排序算法

1. 冒泡排序

1.1 定义

冒泡排序，是比较简单的一种排序算法。

它的命名源于它的算法原理：重复的从前往后（或者从后往前），依次比较记录中相邻的两个元素，如果他们顺序错误就把它们交换过来，直到没有再需要交换的元素，就说明该记录已完成排序。

它看起来就像是把最大的元素（或最小的元素）经由交换慢慢的‘浮’到数列的顶端，故名冒泡排序。

1.2 算法步骤

比较相邻元素，如果第一个比第二个大，就交换它们两个。(升序排序为例)
对每一组相邻元素做同样的工作，从开始到最后一对，这时最后的元素应该会是最大的数。
针对所有元素重复步骤 1,2，除了最后一个元素，这时倒数第二个元素应该会是第二大的数。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

1.3 动图演示

1.4 代码

/**
 * 冒泡排序
 * @param arr 待排序数组
 */
public static void bubbleSort(int[] arr)
{
    int length = arr.length;
    //一个长度为 length 的数列，最多需要进行 length-1 轮比较 外层循环决定需要排序的轮次
    for (int i = 0; i < length - 1; i++)
    {
        //第i轮，需要 length-i-1 次比较 内层循环决定要比较的次数
        for (int j = 0; j < length - 1 - i; j++) 
        {
            if (array[j] > array[j + 1])
            {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

2.插入排序

2.1 定义

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

2.2 算法步骤

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

tips：如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找插入排序。

2.3 动图演示

????‰?

2.4 代码

public static void insert(int[] array)
{
    //通过bound来划分出两个区间
    //[0,bound) 已排序区间
    //[bound,length) 待排序区间
    for (int bound = 1; bound < array.length; bound++)
    {
        //记录当前要比较的元素
        int v = array[bound];
        //记录已排序区间的最后一个元素下标
        int cur = bound - 1;
        //向前找比其大的元素，找到后交换位置
        for (; cur >= 0; cur--)
        {
            if (array[cur] > v)//如果改成>=将变成不稳定排序
            {
                //把cur位置的数据移动到cur+1位置，向后移动一位
                array[cur + 1] = array[cur];
            }
            else
            {
                //否则表示已排好序，直接跳出本次循环
                break;
            }
        }
        //将要排序的元素插到合适的位置(由于最后一次for循环时bound已经减1了，所以需要加1，否则下标越界)
        array[cur + 1] = v;
    }
}

3. 希尔排序（优化插入排序）

3.1 定义

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个数组恰被分成一组，算法便终止。

3.2 算法步骤

把数组按步长gap分组（初始为size/2）
对每组记录采用直接插入排序方法进行排序
缩小gap（gap=gap/2）
当增量减至1时，整个数组恰被分成一组，算法便终止

3.3 动图演示

?¨??o??‘??|???? ??? ?????—?3??¤§??? é???????′??￡? ?

3.4 代码

public static void shell(int[] array)
{
    //初始gap为数组长度/2
    int gap = array.length / 2;
    while (gap >= 1)
    {
        //对每一组使用插入排序
        insert(array, gap);
        //排序后缩小gap
        gap = gap / 2;
    }
}

public static void insert(int[] array, int gap)
{
    //通过bound来划分出两个区间
    //[0,bound) 已排序区间
    //[bound,length) 待排序区间
    for (int bound = gap; bound < array.length; bound++)
    {
        int v = array[bound];
        int cur = bound - gap;//找到同组中的上一个元素
        for (; cur >= 0; cur -= gap)
        {
            if (array[cur] > v)
            {
                array[cur + gap] = array[cur];
            }
            else
            {
                break;
            }
        }
        //插入到合适位置
        array[cur + gap] = v;
    }
}

4. 选择排序

4.1 定义

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。

4.2 算法步骤

先找到序列中最小的数，将它和序列中第一个数交换位置；
接下来，在剩下的序列中继续此操作：找到最小的数，将它和序列中的第二个数交换位置；
依此类推，直到将整个序列排序完成。

简言之，选择排序就是 —— 不断地选择剩余序列中的最小者，然后与未排序数列的“第一个”数字交换位置。

4.3 动图演示

????‰?

4.4 代码

public static void select(int[] arr)
{
    for (int i = 0; i < arr.length; i++)
    {
        //以i位置元素作为擂主，与其后未排序元素比较
        for (int j = i + 1; j < arr.length; j++)
        {
            //打擂成功，交换位置
            if (arr[i] > arr[j])
            {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

5.堆排序

5.1定义

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

什么是堆？（之前的文章也已经介绍，此处只提及部分概念）

堆是一种非线性结构，可以把堆看作一个数组，也可以被看作一个完全二叉树，通俗来讲堆其实就是利用完全二叉树的结构来维护的一维数组但堆并不一定是完全二叉树

按照堆的特点可以把堆分为大顶堆和小顶堆
大顶堆：每个结点的值都大于或等于其左右孩子结点的值
小顶堆：每个结点的值都小于或等于其左右孩子结点的值

下标为i的节点的父节点下标:(i - 1)/2【整数除法】

下标为i的节点的左孩子下标:i×2+1
下标为i的节点的右孩子下标:i×2+2

5.2 算法步骤

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

5.3 动图演示

5.4 代码

public static void heap(int[] arr)
{
    //建立初始堆(大根堆)
    creatHeap(arr);
    //循环把堆顶元素交换到最后，并进行调整
    //当堆中剩一个元素时，已经有序
    for (int i = 0; i < arr.length - 1; i++)
    {
        //交换堆顶元素和最后一个元素
        swap(arr, 0, arr.length - 1 - i);
        //交换完成后调整堆（调整后新的堆大小为arr.length - i - 1）
        shiftDown(arr, arr.length - i - 1, 0);
    }
}

/**
 * 向下调整，构建大根堆（具体构建过程之前已经提及，这里不过多赘述）
 * @param arr
 * @param heapLength
 * @param index
 */
private static void shiftDown(int[] arr, int heapLength, int index)
{
    int parent = index;
    int child = parent * 2 + 1;//左孩子下标
    while (child < heapLength)
    {
        if (child + 1 < heapLength && arr[child + 1] > arr[child])
        {
            child = child + 1;
        }
        if (arr[child] > arr[parent])
        {
            swap(arr, child, parent);
        }
        else
        {
            break;
        }
        parent = child;
        child = parent * 2 + 1;
    }
}

/**
 * 交换堆顶元素和最后一个元素（最后一个元素位置为 arr.length - 1 - i ）
 * @param arr
 * @param i
 * @param j
 */
private static void swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

/**
 * (由于使用向下调整)从最后一个非叶子节点 从后给前 依次调整
 * @param arr
 */
private static void creatHeap(int[] arr)
{
    for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--)
    {
        shiftDown(arr, arr.length, i);
    }
}