算法笔记（二）——排序算法

冒泡排序

冒泡排序相对来说是较为简单的一种排序，它的思想就是在每一次循环中比较相邻的两个数，通过交换的方式，将最小的元素或最大的元素交换到指定位置，举个例子：

将 50 34 19 18 47 按从小到大排序

• 首先比较50与34，如果前者大于后者，那么交换两个数的位置，以便让大的数慢慢移到后面，因此交换50与34；
• 比较50与19，大的移到后面，因此交换；
• 当比较到第5次时，47已经是最后一个数了，交换50与47后，第一次循环就结束了，这时候找到了最大的元素50，并将50放在了最右的位置，50已经排好序了。
• 继续从头开始比较，如果满足条件就交换，直到第8次比较，这时47是最后一个未排序的数，因此此次循环到这里就结束了，因为50已经排好序没必要再比较了；
• 重复以上过程直至全部排序完成。

整个排序过程如下：

观察排序过程我们发现：

1. 对于a这个数组，长度为5，只要进行4次循环比较就能完成任务，（1234）为第一个循环，（567）为第二个，（89）为第三个，（10）为第四个，因此外循环的次数等于数组长度减1。
2. 内循环下标每次从0开始，到a.length-i-1结束，i为外循环循环变量（从0开始）。

由以上两点就可以写出代码了：

public void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]){
                    //swap函数用于交换数组中下标为i和j的两个元素
                    swap(array,j,j+1);
                }
            }
        }
    }

选择排序

选择排序的思想是，每次循环找到当前循环的最大或者最小的元素，并将它与指定位置的元素进行交换。

下图表示一个数组选择排序的过程

• i=0时，当前最小的元素应该被放置在下标0的位置（紫色），于是在下标从0到9中找出最小的元素，找到的最小值为4（红色），将最小值与紫色位置进行交换，此时4已经归位；
• i=1时，此时当前最小元素应该被放置在下标1的位置（紫色），于是在下标1到9中找出最小元素，找到的最小值为6（红色），将下标1与6位置的元素进行交换，此时4与6都已经排序完成；
• 重复上述过程直到所有元素均排序完成。

由以上过程可以发现选择排序的特点：

1. 外循环的次数为数组的长度(a.length)。
2. 每次循环中，需要在下标从i到a.length-1之间找出最小值。
3. 交换最小值与下标i位置的元素。

由此可以写出代码：

public static void selectSort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            //记录当前循环中最小元素的下标
            int minIndex = i;
            for (int j = i; j < a.length; j++) {
                if (a[j] < a[minIndex]) {
                    minIndex = j;
                }
            }
            //交换最小值与下标i位置的元素
            swap(a, minIndex, i);
        }
    }

选择排序改进

既然选择排序的时候是每次找最小值，然后交换，那么反正找最小值的过程要遍历一个数组，能不能在找最小值的过程中顺便将最大值也一起找了呢？然后将最小值放在最前面，最大值放在最后面，不就实现了一个循环排好两个元素了吗？

改进的排序算法过程如下：

i为循环次数，min、max分别代表当前循环中最小值与最大值的下标。这里为了看的更清楚，所以将交换最小值与最大值分别画出来了，实际上找最大值与最小值是在一次循环中完成的。

但是在交换最大值与最小值的过程中有一个细节需要注意，如果出现了这种情况：

2和87已经排好序了，那么交换了最小值后（将4与45交换），这时再交换最大值时就会出错，此时max指向的元素已经被交换了，此时最大值的位置应该在min指向的位置，因此交换最大值的时候实际交换的应该是15和min指向的元素。

由此可以写出改进后的代码：

public static void selectSortImpv(int[] a) {
    //循环次数为原先的一半
    for (int i = 0; i < a.length / 2; i++) {
        //最小元素的下标
        int minIndex = i;
        //最大元素的下标
        int maxIndex = i;
        for (int j = i + 1; j < a.length - i; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
            if (a[j] >= a[maxIndex]) {
                maxIndex = j;
            }
        }
        //交换最小元素
        Utils.swap(a, minIndex, i);
        if (maxIndex == i) {
            swap(a, a.length - i - 1, minIndex);
        } else {
            swap(a, a.length - i - 1, maxIndex);
        }
        printArray(a);
    }
}

插入排序

插入排序的思想跟扑克牌理牌的方法一样，比如跟朋友玩斗地主的时候，扑克牌全部发完后，每个人拿自己的一摞牌理牌，回想一下我们是怎么理牌的，先抽出第一张放在手中，再抽出第二张，如果比第一张小就放在第一张的左边，否则放在右边，再抽出第三张牌，看它适合放在哪两张牌之间（或者最左边最右边）就插入进去，重复这样的过程直到抽完所有牌，这样自己的牌就排序好了。

还是以之前的数组排序为例看一下插入排序的过程：

• 首先第一个数不需要排序，从第二个数开始，34比40小，那么需要在34前面的位置（下标为0，红色区域）将34插入进去
• 那么先将34提出来（黑色方框），然后把40往后移一位，这样空出了①位置，这个位置就是34应该放置的位置，因此把34放在该位置。
• 然后看第三个元素19，19比前一个元素40小，因此需要在19前面（下标从0到1，红色区域）找到19应该插入的位置。
• 将19提出来（黑色方框），然后把40往后移，空出了②位置。
• 19再与前面一个值34比较，19小与34，所以19不能放在②位置，将34完后移一位，空出了③位置，这时19放在该位置是符合要求的，因此把19放在该位置。
• 重复以上步骤直到最后一个元素插入完成。

插入排序的过程简单来说就是：

1. 第一个元素不需要排序，循环从1开始。
2. 如果当前元素a[i]比前一个元素大，那么不需要变动位置。
3. 如果当前元素a[i]比前一个元素小，那么将当前元素提出来，并在这个元素前（下标从0到i-1）找到一个合适插入位置j。
4. 将下标j与i-1之间（包括i-1）的元素统统往后移一个位置，以便腾出一个空间。
5. 将当前元素放入腾出的空间a[j]中。

以下是一个数组插入排序的完整过程：

插入排序的代码如下：

public static void insertSort(int[] a){
        //第一个元素不用操作，循环从1开始
        for (int i = 1; i < a.length; i++) {
            //如果当前元素大于前一个元素，那么已经是有序的，不作处理
            if(a[i] > a[i- 1]){
                continue;
            }else{
                //将当前元素取出
                int temp = a[i];
                //在下标为0到i-1中查找该元素应该插入的位置
                for (int j = 0; j < i; j++) {
                    if(a[j] >= temp){
                        //查找到插入位置为下标j，将下标j到i的元素往后移位，以把下标j位置空出来
                        for (int k = i; k > j ; k--) {
                            a[k] = a[k-1];
                        }
                        //将当前元素放在下标j位置
                        a[j] = temp;
                        break;
                    }
                }
            }
        }
    }

这里找插入位置使用的是从左到右顺序查找，即从0查找到i-1，如果中间有满足的位置那么查找结束，可以使用二分查找进行优化。

希尔排序

希尔排序是一种基于插入排序的排序算法。对于大规模的数组，插入排序很慢，因为它需要进行大量的移位操作，元素只能一点一点地从数组一端移动到另一端。我们知道插入排序对内部有序的数组来说效率是非常高的，所以希尔排序的思想将数组内部逐渐变得有序，这样为插入排序创造一个好的条件，再使用插入排序的时候就能省去很多移位操作。

先来看一个概念：

h有序数组：数组中任意间隔h的元素都是有序的。举个例子，h=3的时候，假设数组a长度为8，那么如果a[0],a[3],a[6]是有序的，a[1],a[4],a[7]是有序的，a[2],a[5]是有序的，就可以称a数组是3有序数组

下面以一个例子看看希尔排序的过程：

• 数组的长度为10，如果先将h设为5（数组长度一半）的话，那么可以将数组拆分成5个长度为2的子数组（第一个框框，黑色部分），分别对这5个子数组进行插入排序，得到排序后的子数组（第一个框框，红色部分）。
• 子数组排序后，原数组就变成了5有序数组了（第二个框框第一行），这时候缩小h，将h设置为2（原来h的一半），那么可以将原数组拆分成2个长度为5的数组（第二个框框，黑色部分），对这两个子数组再使用插入排序，得到排序后的子数组（第二个框框，红色部分）。
• 经过上一步，原数组已经是2有序数组了（第三个框框，第一行），继续缩小h，将h设置为1，其实就是对原数组直接进行插入排序了，这样排序完成后，整个数组就排序完成了（第三个框框，红色部分）。不用再缩小h了（这不是废话嘛= =）。

结合上述过程再看代码就比较清晰了，代码如下：

public static void shellSort(int[] a) {
    //刚开始h为数组长度一半
    int h = a.length / 2;
    //如果h<1的话，结束循环，数组已经排序完成
    while (h >= 1) {
        //使用插入排序对子数组进行排序
        shellInsert(a, h);
        //将h的值缩小一半
        h = h / 2;
    }
}
private static void shellInsert(int[] a, int h) {
    //分别对每个子数组操作，总共有h个子数组
    for (int i = 0; i < h; i++) {
        //每个子数组进行插入排序
        for (int j = i+h; j < a.length; j += h) {
            int temp = a[j];
            int k = j - h;
            //找到当前元素应该被插入的位置j
            for (; k >= i; k-=h) {
                if(a[k] >= temp) {
                    a[k + h] = a[k];
                }else{
                    break;
                }
            }
            //将当前元素放入插入位置
            a[k + h] = temp;
        }
    }
}

像上述h的取值为1，2，5这样的序列叫递增序列，选择合适的递增序列有助于提升希尔排序的效率，我看的算法书中建议使用1，4，13，40，121，364……这样的递增序列，公式为h=3*h+1

归并排序

归并排序是典型的分治思想，将一个数组分成两个排序过的数组，然后对这两个数组进行归并就能得到排序后的数组。而两个子数组又可以通过这样的方式继续拆分下去，直到每个数组中只有一个元素。

归并

归并的功能是，将两个有序数组合并成一个有序数组。比如下面的例子：

红色为第一个数组，绿色为第二个数组，两个数组内的元素都是从小到大排列，怎么将这样两个数组合并成一个大的数组？

• 新建一个用于保存最终结果的临时数组temp，长度为两个数组的长度之和；
• 使用两个指针，i指向第一个数组首元素18，j指向第二个数组首元素4，比较a[i]和b[j]的大小；
• b[j]小，那么把b[j]放入临时数组中temp[0]的位置，此时b数组中4已经添加过了，将j指向下一个元素24(j++)，再次比较a[i]和b[j]大小。
• a[i]小，那么把a[i]放入临时数组中temp[1]的位置，此时a数组中18已经添加过了，将i指向下一个元素19(i++)，再次比较a[i]和b[j]大小。
• a[i]小，那么把a[i]放入临时数组中temp[2]的位置，此时a数组中19已经添加过了，将i指向下一个元素34(i++)，再次比较a[i]和b[j]大小。
• 重复以上过程，如果碰到某一个数组中的元素已经全部添加完了（i==a.length || j==b.length），那么将另一个数组的剩下的元素直接添加到temp后面，比如上图倒数第二行，此时a中元素已经添加完了，b中还剩两个元素，那么直接将42，47放到temp[5]，也就是40后面。

/**
 * 归并操作
 * @param a     数组
 * @param left  第一个子数组首元素下标
 * @param mid   第一个子数组尾元素下标
 * @param right 第二个子数组尾元素下标
 */
private static void merge(int[] a, int left, int mid,
    //临时数组用于保存合并后的数组
    int[] temp = new int[right - left +1];
    //指向左边数组的指针
    int first  = left;
    //指向右边数组的指针
    int second = mid+1;
    //临时数组的指针
    int tempIndex = 0;
    //如果两个数组指针都没有出界，即两个数组中都还有未添加的元素
    while(first <= mid && second <= right) {
        if (a[first] <= a[second]) {
            temp[tempIndex] = a[first];
            tempIndex++;
            first++;
        } else {
            temp[tempIndex] = a[second];
            second++;
            tempIndex++;
        }
    }
    //如果一个数组已经全部加入到临时数组中，另一个数组剩下的部分直接放到临时数组后
    if(first == (mid+1)){
        for(;second<= right;second++){
            temp[tempIndex] = a[second];
            tempIndex++;
        }
    }
    if(second == (right+1)){
        for(;first<= mid;first ++){
            temp[tempIndex] = a[first];
            tempIndex++;
        }
    }
}

自底向上的归并排序

自底向上的归并排序的思想可以看下图：

1. 如果一个数组中只有一个元素的话，那么它肯定是有序的（这也是废话，一个元素何来排序）。所以我们将每个元素看成一个长度为1的数组，这样就能用归并操作对这两个数进行排序了。因此将原数组两两一组，分别进行归并，如果最后剩下一个就不用归并了，这样得到的数组如标号1的那行所示。
2. 经过上一步，数组中已经红色部分和绿色部分都是已经排好序的了，那么再讲这些排好序的部分两两一组进行归并，就会得到标号2那行的数组，此时红色和绿色部分已经是排好序了。可以看到归并操作正在将有序的部分逐渐扩大。
3. 重复以上步骤，直到合并的两个数组形成的新数组长度正好等于原数组的时候，原数组就排序好了。

对于一个具体的数组来说，归并的过程的执行次序如下：

自顶向下的归并排序

自顶向下的归并需要用到递归的思想，对于一个未排序的数组，我们想对它进行排序，这个排序函数应该怎么调用？

首先先确定参数形式:

sort(int[] a,int left,int right)

a为数组，left，right分别为要排序的开始下标和结束下标。

那么递归的边界条件是什么？我们知道如果数组中只有一个元素就不用排序了，因此如果left与right相等，那么就不用再递归调用了，直接退出就好了。所以完成代码如下：

private static void sort(int[] a,int left,int right){
    if(left == right){
        return ;
    }
}

然后对于一般情况，我们要做的是什么？联系一下归并函数merge的参数，我们想到，将一个数组分成两半，对这两半分别进行排序，再将排序后的数组合并。由此写出下面的代码：

private static void sort(int[] a,int left,int right){
    if(left == right){
        return ;
    }
    int mid = (left + right) / 2;
    //对左半边进行排序
    sort(a,left,mid);
    //右半边
    sort(a,mid+1,right);
    //将左右两个数组合并
    merge(a,left,mid,right);
}

归并排序的全部代码：

public static void mergeSort(int[] a){
    sort(a,0,a.length-1);
}
private static void sort(int[] a,int left,int right){
    if(left == right){
        return ;
    }
    int mid = (left + right) / 2;
    //对左半边进行排序
    sort(a,left,mid);
    //右半边
    sort(a,mid+1,right);
    //将左右两个数组合并
    merge(a,left,mid,right);
}
/**
 * 归并操作
 * @param a     数组
 * @param left  第一个子数组首元素下标
 * @param mid   第一个子数组尾元素下标
 * @param right 第二个子数组尾元素下标
 */
private static void merge(int[] a, int left, int mid, int right) 
    //临时数组用于保存合并后的数组
    int[] temp = new int[right - left +1];
    //指向左边数组的指针
    int first  = left;
    //指向右边数组的指针
    int second = mid+1;
    //临时数组的指针
    int tempIndex = 0;
    while(first <= mid && second <= right) {
        if (a[first] <= a[second]) {
            temp[tempIndex] = a[first];
            tempIndex++;
            first++;
        } else {
            temp[tempIndex] = a[second];
            second++;
            tempIndex++;
        }
    }
    //如果一个数组已经全部加入到临时数组中，另一个数组剩下的部分直接放到临时数组后
    if(first == (mid+1)){
        for(;second<= right;second++){
            temp[tempIndex] = a[second];
            tempIndex++;
        }
    }
    if(second == (right+1)){
        for(;first<= mid;first ++){
            temp[tempIndex] = a[first];
            tempIndex++;
        }
    }
    //将临时数组的值赋给原数组
    for (int i = 0; i < temp.length; i++) {
        a[i+left] = temp[i];
    }
}

以一个数组为例，程序的执行流程如下：

函数执行顺序	合并示意图

可以看到对于每次递归调用sort都是先排序左边，再排序右边，再合并左边与右边。

快速排序

快速排序也是一种分治算法，它也是将一个数组分成左右两个数组，将两部分独立地排序。快速排序跟归并排序的区别是：归并排序是先将数组分成两个子数组，对两个子数组分别排序后再合并。快速排序省去了归并排序的合并操作，当两个子数组有序的时候，整个数组就有序了；在归并排序中，递归调用发生在处理数组之前，也就是上文中sort函数在merge函数之前，而快速排序中，递归调用发生在处理整个数组之后，这个咱们之后联系代码再看；归并排序是将数组等分成两半，再快速排序中，切分(partition)的位置取决于数组的内容。

切分

切分实现的是这样的功能，选定一个基准元素（后直接称pivot），将数组中不大于pivot的都放到它的左边，不小于pivot的放到它的右边。以下面的图为例，pivot取的是首元素40（紫色），进行切分后，40左边红色的部分都是不大于40的，40右边绿色的部分都是不小于40的。如果红色与绿色部分分别都是有序的，那么整个数组就是有序的了（第三行）。

下面来看看切分的具体步骤：

1. 使用一个左指针（红色）和右指针（绿色），左指针指向pivot的下一个，右指针指向最后一个元素。
2. 左指针从左到右找第一个不小于pivot的元素（47），右指针从右往左找第一个不大于pivot的元素（11）。
3. 如果两个指针没有相遇或者移到边界，那么交换两个元素（蓝色）。
4. 如果两个指针相遇或是移到边界，那么结束循环，最后将pivot与右指针指向的元素互换（蓝色）。

为什么不是左指针而是右指针呢？这个与选的pivot有关，如果选的是最左边的元素，那么就是右指针；如果pivot选的是最右边的元素，那么交换的就是左指针了。从图中也能看出来，左右指针相遇时，左指针指向的是42，右指针指向的是24，如果是交换42和40明显就不对了。

下面是切分的示意图：

下面给出切分的代码，对照切分的步骤应该不难理解：

public static int partition(int[] a,int left,int right){
    //取最左边的元素作为基准元素
    int pivotValue = a[left];
    //左指针
    int i = left+1;
    //右指针
    int j = right;
    while (true) {
        //左指针从左到右找第一个不小于pivot的元素
        while (a[i] <= pivotValue) {
            //指针移到边界
            if(i == right){
                break;
            }
            i++;
        }
        //右指针从右往左找第一个不大于pivot的元素
        while (a[j] > pivotValue) {
            //指针移到边界
            if(j == left){
                break;
            }
            j--;
        }
        //左右指针相遇
        if (i>= j){
            break;
        }
        //交换左右指针指向的元素
        swap(a,i,j);
    }
    //最后交换右指针与pivot
    swap(a,left,j);
    //返回值为pivot所在的下标位置
    return j;
}

快速排序过程

了解了切分的过程后，快排的思想就出来了，同归并一样，考虑递归的执行过程。对于一个数组，要先进行切分，将数组切分成左右两个数组，再分别对左右两个数组进行排序，而这个排序又是先切分，再对左右进行排序。于是我们能写出这样的代码：

public static void sort(int[] a,int left,int right){
    if(left>=right){
        return ;
    }
    //返回排序后pivot所在下标位置
    int pivot = partition(a,left, right);
    //对pivot左边元素进行排序
    sort(a,left,pivot-1);
    //对pivot右边元素进行排序
    sort(a,pivot+1,right);
}

对于一个具体的例子，快速排序的示意图与流程如下：

快排示意图	实际执行顺序

下面是快速排序的完整代码：

/**
 * 快速排序，选取最左边元素作为基准元素
 * @param a
 */
public static void quickSort(int[] a){
    sort(a,0,a.length-1);
}
public static void sort(int[] a,int left,int right
    if(left>=right){
        return ;
    }
    //返回排序后pivot所在下标位置
    int pivot = partition(a,left, right);
    //对pivot左边元素进行排序
    sort(a,left,pivot-1);
    //对pivot右边元素进行排序
    sort(a,pivot+1,right);
}
public static int partition(int[] a,int left,int r
    //取最左边的元素作为基准元素
    int pivotValue = a[left];
    //左指针
    int i = left+1;
    //右指针
    int j = right;
    while (true) {
        //左指针从左到右找第一个不小于pivot的元素
        while (a[i] <= pivotValue) {
            //指针移到边界
            if(i == right){
                break;
            }
            i++;
        }
        //右指针从右往左找第一个不大于pivot的元素
        while (a[j] > pivotValue) {
            //指针移到边界
            if(j == left){
                break;
            }
            j--;
        }
        //左右指针相遇
        if (i>= j){
            break;
        }
        //交换左右指针指向的元素
        swap(a,i,j);
    }
    //最后交换右指针与pivot
    swap(a,left,j);
    //返回值为pivot所在的下标位置
    return j;
}

参考资料

1. 《算法》
2. 面试中的排序算法总结