常见排序算法详解

前言

作为程序员，时时刻刻都要与算法打交道，其中排序算法算是比较常见的一种。而在面试程序员岗位中， 不出意外，排序算法也是比较常见的考量之一。因此我们有必要了解和掌握各种常见排序算法。
这个篇文章记录了几种常见的排序算法，并各种排序算法极端情况的优劣想，供学习和参考。

介绍

对数据进行排序意味着以特定顺序排列数据，通常是在类似数组的数据结构中。您可以使用各种排序标准，常见的排序标准是从最小到最大排序数字，反之亦然，或按字典顺序排序字符串。

常见的几种排序算法

• 冒泡排序
• 选择排序
• 插入排序
• 归并排序
• 快速排序
• 堆排序

算法介绍

一、冒泡排序

冒泡排序通过交换相邻元素（如果它们不是所需的顺序）来工作。此过程从数组的开头重复，直到所有元素都按顺序排列。

bubble-sort.gif

举例
对4 2 1 5 3进行排序:

1. 4 2 1 5 3 : 前两个元素的顺序错误，所以我们交换它们。
2. 2 4 1 5 3 : 后两个元素也是错误的顺序，所以我们交换。
3. 2 1 4 5 3 : 这两个是正确的顺序，4 <5，所以我们不管它们。
4. 2 1 4 5 3 : 另一次交换。

2 1 4 3 5 :这是一次迭代后得到的数组。
因为在第一次传递期间至少发生了一次交换（实际上有三次），我们需要再次遍历整个数组并重复相同的过程。
通过重复这个过程，直到不再进行交换，我们将有一个排序的数组。

代码实现

public void bubbleSort(int[] array) {  
    boolean sorted = false;
    int temp;
    while(!sorted) {
        sorted = true;
        for (int i = 0; i < array.length - 1; i++) {
            if (a[i] > a[i+1]) {
                temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                sorted = false;
            }
        }
    }
}

二、选择排序

选择排序是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完

selection-sort.gif

举例
对4 2 1 5 3进行排序:

1. 4 2 1 5 3 : 未排序状态
2. 1 4 2 5 3 : 选择最小值1, 排入第一位
3. 1 2 4 5 3 : 从第二位开始, 选择最小值2, 排入第二位
4. 1 2 3 4 5 : 从第三位开始,选择最小值3, 排入第三位
5. 1 2 3 4 5 : 从第四位开始, 选择最小值4, 排入第四位
6. 1 2 3 4 5 : 从第五位开始,选择最小值5, 排入第五位

至此排序结束。

代码实现

public void selectionSort(int[] array) {  
    for (int i = 0; i < array.length; i++) {
        int min = array[i];
        int minId = i;
        for (int j = i+1; j < array.length; j++) {
            if (array[j] < min) {
                min = array[j];
                minId = j;
            }
        }
        // 交换
        int temp = array[i];
        array[i] = min;
        array[minId] = temp;
    }
}

三、插入排序

插入排序是将数组划分为已排序和未排序的子数组。
排序部分的开头长度为1，对应于数组中的第一个（最左侧）元素。我们遍历数组，在每次迭代中，我们将数组的排序部分扩展一个元素。
在扩展时，我们将新元素放置在已排序子阵列中的适当位置。我们通过将所有元素向右移动直到遇到我们不必移动的第一个元素来实现这一点。

insertion-sort.gif

举例
对3 5 7 8 4 2 1 9 6进行排序:

1. 3 5 7 8 4 2 1 9 6 : 我们采取4并记住这是我们需要插入的。从8> 4开始，我们转移。
2. 3 5 7 x 8 2 1 9 6 : x的值不是至关重要的，因为它将被立即覆盖（如果它是适当的位置则为4或如果我们移位则为7）。从7> 4开始，我们转移。
3. 3 5 x 7 8 2 1 9 6
4. 3 x 5 7 8 2 1 9 6
5. 3 4 5 7 8 2 1 9 6

在这个过程之后，排序的部分被一个元素扩展，我们现在有五个而不是四个元素。每次迭代都会这样做，最后我们将对整个数组进行排序。

代码实现

public void insertionSort(int[] array) {  
    for (int i = 1; i < array.length; i++) {
        int current = array[i];
        int j = i - 1;
        while(j >= 0 && current < array[j]) {
            array[j+1] = array[j];
            j--;
        }
       
        array[j+1] = current;
    }
}

四、归并算法

合并排序/归并算法使用递归来解决比先前提出的算法更有效的排序问题，特别是它使用分而治之的方法。
使用这两个概念，我们将整个数组分解为两个子数组，然后：
1、对数组的左半部分进行排序（递归）
2、对数组的右半部分进行排序（递归）
3、合并解决方案

merge-sort.gif

举例
对3 5 4 2 1 进行排序:

sorting-algorithms-in-java.png

此树表示递归调用的工作方式。标有向下箭头的数组是我们需要排序的数组，而向上箭头的数组是我们合并完后的数据。所以先按下递归向下箭头数组到树的底部，然后向上返回并合并。

在我们的例子中，我们有数组3 5 3 2 1，所以我们把它分成3 5 4和2 1。为了对它们进行排序，我们进一步将它们分成它们的组 一旦我们到达底部，我们就开始合并并按照我们的方式对它们进行排序

代码实现

public void mergeSort(int[] array, int left, int right) {  
    if (right <= left) return;
    int mid = (left+right)/2;
    mergeSort(array, left, mid);
    mergeSort(array, mid+1, right);
    merge(array, left, mid, right);
}

private void merge(int[] array, int left, int mid, int right) {
    // 计算长度
    int lengthLeft = mid - left + 1;
    int lengthRight = right - mid;

    // 创建临时数组
    int leftArray[] = new int [lengthLeft];
    int rightArray[] = new int [lengthRight];

    // 将需要排序的数组分别传入左右两个临时数组里
    for (int i = 0; i < lengthLeft; i++)
        leftArray[i] = array[left+i];
    for (int i = 0; i < lengthRight; i++)
        rightArray[i] = array[mid+i+1];

    // 左右临时数组当前索引
    int leftIndex = 0;
    int rightIndex = 0;

    // 将左右临时数组重新按从小到大顺序写入待排序数组中
    for (int i = left; i < right + 1; i++) {
        // 如果R和L中仍然有未复制的元素，则复制这两个元素的最小值
        if (leftIndex < lengthLeft && rightIndex < lengthRight) {
            if (leftArray[leftIndex] < rightArray[rightIndex]) {
                array[i] = leftArray[leftIndex];
                leftIndex++;
            }
            else {
                array[i] = rightArray[rightIndex];
                rightIndex++;
            }
        }
        // 如果所有元素都已从rightArray复制，则复制left Array的其余部分
        else if (leftIndex < lengthLeft) {
            array[i] = leftArray[leftIndex];
            leftIndex++;
        }
        // 如果所有元素都已从leftArray复制，则复制right Array的其余部分
        else if (rightIndex < lengthRight) {
            array[i] = rightArray[rightIndex];
            rightIndex++;
        }
    }
}

五、快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

quick-sort.gif

举例
对6 1 2 7 9 3 4 5 10 8 进行排序:
首先取基准数, 每一轮的排序要义是将数组以基准数为准,将数组分为左右两个部分, 左边部分都比基准数小, 右边部分都比基准数大。

1. <u>6</u> 1 2 7 9 3 4 5 10 8 : 取6为基准数
2. <u>6</u> 1 2 <u>7</u> 9 3 4 5 10 8 : 先从左向右搜索,获取比6大的数7,记录下来。
3. <u>6</u> 1 2 <u>7</u> 9 3 4 <u>5</u> 10 8 : 接着从右向左搜索, 获取比6小的数 5, 记录下来。
4. <u>6</u> 1 2 5 9 3 4 7 10 8 : 将第二步和第三步记录下来的两个数进行交换。
5. <u>6</u> 1 2 5 <u>9</u> 3 4 7 10 8 : 以第二步搜索停止位置接着向右搜索, 获取比6大的数9, 记录下来。
6. <u>6</u> 1 2 5 <u>9</u> 3 <u>4</u> 7 10 8 : 以第三步搜索停止位置接着向左搜索, 获取比6小的数4, 记录下来。
7. <u>6</u> 1 2 5 4 3 9 7 10 8 : 将第五步和第六步记录下来的两个数进行交换。
8. *** <u>3 1 2 5 4</u> 6 <u>9 7 10 8</u>*** : 重复第六步, 发现无可搜索数据, 将最后一个数3 与基准数互换。

至此, 第一轮搜索结束, 基准数6将数组分割成两部分, 接下来,将这两部分按照1-8步骤, 分别进行排序, 直至无法切分,则排序完成。
摘用网上图片:

quick-sort-1.jpg

代码实现

public void quickSort(int[] array, int begin, int end) {  
    if (end <= begin) return;
    int pivot = partition(array, begin, end);
    quickSort(array, begin, pivot-1);
    quickSort(array, pivot+1, end);
}

private int partition(int[] array, int begin, int end) {  
    int baseValue = array[begin];
    int leftIndex = begin + 1;
    int rightIndex = end;
    int temp;
    
    while(leftIndex != rightIndex) {
        //先从左边向右搜索
        while(array[leftIndex] <= baseValue && leftIndex < rightIndex) {
            leftIndex ++;
        }
        //再从右边向左搜索
        while(rightIndex] >= baseValue && leftIndex <    rightIndex) {
            rightIndex --;
        }
        
        //交换两个数的位置
        if (leftIndex < rightIndex) {
            temp = array[leftIndex];
            array[leftIndex] = array[rightIndex];
            array[rightIndex] = temp;
        }
    }
    
    //最终将基准数归位 
    array[begin] = array[leftIndex];
    array[leftIndex] = baseValue;

    //返回基准数位置
   return leftIndex;
}

六、堆排序

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

heap-sort.gif

堆分两种:

1. 大顶堆

   
   大顶堆.jpg

每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
数组书写方式: 8 7 6 5 4 3
其中: arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

2. 小顶堆

   
   小顶堆.jpg

每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
数组书写方式: 3 4 5 6 7 8
其中: arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

以下介绍我们都默认以大顶堆为准。

堆排序的基本思路：

1. 将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
2. 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

代码实现

public void heapSort(int[] array) {  
    if (array.length == 0) return;

    // 构建大顶堆
    int length = array.length;
    for (int i = length / 2-1; i >= 0; i--) {
        heapify(array, length, i);
    }
       

    for (int i = length-1; i >= 0; i--) {
        int temp = array[0];
        array[0] = array[i];
        array[i] = temp;
        //重新构建大顶堆
        heapify(array, i, 0);
    }
}

private void heapify(int[] array, int length, int i) {  
    int leftChild = 2*i+1;
    int rightChild = 2*i+2;
    int largest = i;

    // 如果左节点大于父节点
    if (leftChild < length && array[leftChild] > array[largest]) {
        largest = leftChild;
    }

    // 如果右节点大于父节点
    if (rightChild < length && array[rightChild] > array[largest]) {
        largest = rightChild;
    }

    // 如果需要则交换
    if (largest != i) {
        int temp = array[i];
        array[i] = array[largest];
        array[largest] = temp;
        heapify(array, length, largest);
    }
}

算法比较

名称	最好情况	平均情况	最坏情况	额外空间	稳定性
冒泡排序				1	稳定
选择排序				1	不稳定
插入排序				1	稳定
归并排序				n	稳定
快速排序					不稳定
插入排序				1	不稳定

我们在10,000个整数的随机数组副本上,以上诉几种算法进行测试,结果如下：

时间（NS）	冒泡排序	插入排序	选择排序	归并	堆排序	快速排序
第一次运行	266089476	21973989	66603076	5511069	5283411	4156005
第二轮	323692591	29138068	80963267	8075023	6420768	7060203
第三次运行	303853052	21380896	91810620	7765258	8009711	7622817
第四次运行	410171593	30995411	96545412	6560722	5837317	2358377
第五次运行	315602328	26119110	95742699	5471260	14629836	3331834
第六次运行	286841514	26789954	90266152	9898465	4671969	4401080
第七次运行	384841823	18979289	72569462	5135060	10348805	4982666
八跑	393849249	34476528	107951645	8436103	10142295	13678772
第九跑	306140830	57831705	138244799	5154343	5654133	4663260
第十次运行	306686339	34594400	89442602	5601573	4675390	3148027

仅以此样本为例, 冒泡排序在性能方面是最差的, 堆排和快排性能最佳

总结

对数据集进行排序是一种非常常见的操作，无论是进一步分析它们，还是使用依赖于排序数据的更有效算法来加速搜索，过滤数据等。