六大排序算法的总结

原文始发于微信公众号（BeCoder）：面试常考排序算法的全面总结

 

各大互联网公司在面试时都会考察一些算法，最常见的便是排序算法，基本的如冒泡排序，难一点的有快速排序、归并排序等。

这篇文章就给大家整理一下常考排序算法的相关知识。

 

进入正题之前先掌握两个概念，后面需要用到。

【稳定排序】

序列中两个相同元素在排序之前与排序之后的相对位置不变。

举个栗子：待排序列 1 3 1 4 5 2 0，第一个元素1与第三个元素1是相同的，稳定排序会使它们在排序前与排序后的相对位置不变。

反之就是不稳定排序

 

【精俭排序】

一对数字不会进行两次或者两次以上的比较。

 

 

冒泡排序

 

冒泡排序是交换排序的一种，这是最基本的，也是大家最熟悉的排序算法。

算法思路

从一端开始，依次比较两相邻元素，若倒序则交换。

示例图

性质

1. 每趟排序都会把较大的数“冒”到右边（图中红色数字）。

2. 若待排序列元素个数为n，则需要进行n-1趟排序（可以这样理解：根据第1条性质，n-1趟排序能“冒”出n-1个数，那么剩下1个数肯定会在正确位置，就不用再“冒”一次了）。

3. 每趟排序的比较次数为n-i，i为排序的趟数，如：6个待排元素，需要5趟排序，第4趟排序的比较次数为6-4=2.

4. 稳定排序；因为两元素若相同，比较之后不会进行交换。

5. 平均时间复杂度为O(n^2)；因为排序趟数所需时间复杂度为O(n)，每趟排序比较交换也为O(n)。

6. 空间复杂度为O(1)；就地排序，没有用到额外空间。

7. 元素的移动次数（算法的性能）和元素初始排列次序有关。

再补充一下：上图示例中的待排数据比较巧合，导致第③趟排序后数据就已经有序了，但实际上后续排序仍会进行，这也可以看出冒泡排序效率很低。

 

代码

    public static void bubbleSort(int[] arr){        for(int i=0;i<arr.length-1;i++){            for(int j=0;j<arr.length-1-i;j++){                if(arr[j+1]<arr[j]){                    int temp = arr[j+1];                    arr[j+1] = arr[j];                    arr[j] = temp;                }            }        }    }

 

插入排序

 

全称为直接插入排序，是插入排序的一种，在没有指明的情况下，我们所说的插入排序默认是指直接插入排序。

算法思路

将待排序列分成无序和有序两部分，第一部分是待排序列第一个元素（看作有序），第二部分是剩下元素（看作无序），每次排序时从无序序列中拿出第一个元素插到有序序列的合适位置。

示例图

性质

1. 稳定排序；若两元素相同，会把插入元素放在被插入元素的后面，两者相对位置不变。

2. 某一趟排序结束后未必能选出一个数放在其最终位置上；这个容易理解，因为后面插进来的元素插入到有序序列时会改变其后元素的位置。

3. 精俭排序；两元素之间只会进行1次比较。

4. 元素的移动次数（算法的性能）和初始排列次序有关。

5. 平均时间复杂度为O(n^2)。

6. 空间复杂度为O(1)。

代码

    public static void insertSort(int[] arr){        for(int i=1;i<arr.length;i++){            for(int j=i;j>0;j--){                if(arr[j]<arr[j-1]){                    int temp = arr[j];                    arr[j] = arr[j-1];                    arr[j-1] = temp;                }            }        }    }

 

选择排序

 

全称为简单选择排序，是选择排序的一种，在没有指明的情况下，我们所说的选择排序默认是指简单选择排序。

算法思路

第一次从待排序列中选出一个最小的数放在待排序列的起始位置，接着在剩余未排序序列中选出最小的数放到已排序序列的末尾，以此类推，直至未排序序列元素个数为0.

 

示例图

性质

1. 不稳定排序；举个栗子：待排序列 3 7 3 1 5，第一次排序时第一个元素3会和元素1交换位置，显然改变了两个相同元素3的相对位置。

2. 平均时间复杂度为O(n^2)。

3. 空间复杂度为O(1)。

    

代码

    public static void selectSort(int[] arr){        for(int i=0;i<arr.length-1;i++){            int min = i;            for (int j=i+1;j<arr.length;j++){                if(arr[min]>arr[j]){                    min = j;                }                if(min!=i){                    int temp = arr[min];                    arr[min] = arr[i];                    arr[i] = temp;                }            }        }    }

 

快速排序

 

快排大概是面试中考得最多的一种排序算法了吧，和冒泡排序一样，它也是交换排序的一种，是对冒泡排序的一种改进。

算法思路

使用“分治”的思想，找到一个主元（一般使用第1个元素），将待排序列分为左右两部分，左边元素都比主元小，右边元素都比主元大；接着分别对左右两序列也进行上述操作（即选主元，分序列），直至待排序列有序。

示例图

我按照图中示例给大家说一下整个流程。

1. 选择第一个元素7作为主元，并定义两个指针（图中绿色和紫色箭头），分别指向开头和末尾。

2. 紫色箭头先移动，找到第一个比7小的元素2；绿色箭头接着移动，找到第一个比7大的元素9.

3. 交换9和2的位置。

4. 再次进行第2步操作，找到8和4.

5. 交换8和4的位置。

6. 此时紫色箭头向左移动，发现与绿色箭头重合了，并指向元素4.

7. 将主元7和元素4交换位置。

8. 至此，第一趟排序结束了，成功使用主元7将待排序列分为两部分，左边的“4，5，2”比7小，右边的“8，9，10”比7大。

9. 接着分别对左右两序列进行以上全部操作，如此递归下去，直至整个序列有序。

性质

1.不稳定排序；举例：待排序列为 5 3 3 4 3 8 9 10 11， 主元5和第五个元素3交换就会改变三个相同元素3的相对位置。

2.元素的移动次数（算法的性能）和初始排列次序有关。

3.平均时间复杂度为O(nlogn)。

4.空间复杂度为O(logn)；虽然没有用到额外数组，但是递归调用需要使用栈空间。

5.当待排序列基本有序时，快速排序效率很低，时间复杂度会退化成O(n^2)。

6.总体来看，快速排序是效率最高的排序算法，但使用哪种排序算法需要视情况而定。

 

代码

public static int[] qsort(int arr[],int start,int end) {            int pivot = arr[start];            int i = start;            int j = end;            while (i<j) {                    while ((i<j)&&(arr[j]>pivot)) {                            j--;                    }                    while ((i<j)&&(arr[i]<pivot)) {                            i++;                    }                    if ((arr[i]==arr[j])&&(i<j)) {                            i++;                    } else {                            int temp = arr[i];                            arr[i] = arr[j];                            arr[j] = temp;                    }            }            if (i-1>start) arr=qsort(arr,start,i-1);            if (j+1<end) arr=qsort(arr,j+1,end);            return (arr);    }

 

希尔排序

 

插入排序的一种。

算法思路

按照步长（如元素个数的一半）将待排序列分为若干组，每组内使用直接插入排序；每趟排序步长折半，直至序列有序。

 

示例图

性质

1. 不稳定排序；一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱。

2. 某一趟排序结束后未必能选出一个数放在其最终位置上。

3. 平均时间复杂度为O(nlogn)。

4. 空间复杂度为O(1)。

代码

public static void main(String[] args){    int[] array={49,38,65,97,76,13,27,49,78,34,12,64,1};        for(int i=0;i<array.length;i++){            System.out.print(array[i]+" ");        }        //希尔排序        int gap = array.length;        while (true) {                gap /= 2;   //步长每次减半                for (int i = 0; i < gap; i++) {                        for (int j = i + gap; j < array.length; j += gap) {//这个循环里其实就是一个插入排序                                int temp = array[j];                                int k = j - gap;                                while (k >= 0 && array[k] > temp) {                                        array[k + gap] = array[k];                                        k -= gap;                                }                                array[k + gap] = temp;                        }                }                if (gap == 1)                        break;        }        System.out.println();        for(int i=0;i<array.length;i++){            System.out.print(array[i]+" ");        }    }

 

归并排序

 

算法思路

同样也使用了“分治”思想，将待排序列不断分解为多个子序列，然后对相邻子序列两两进行排序，从段内有序到段间有序。

示例图

流程介绍：

1. 不断递归直至将每个元素作为一个子序列。

2. 两个相邻子序列之间进行排序，并合并到新的空间中。

3. 重复第2步直至待排序列有序。

子序列间排序示意图：

1. 申请空间，大小为两个子序列大小之和，该空间用于存放合并后的序列。

2. 定义两个指针（图中红色和绿色箭头），分别指向两个子序列起始位置。

3. 比较两个指针指向的元素，选择较小的放入之前申请的空间中。

4. 并将较小元素所在序列的指针移向下一个位置，重复操作3，直至某一序列指针超出范围。

5. 将另一序列中的剩余元素放进申请的空间中。

按照以上流程不断进行归并，最终使整个待排序列有序。

性质

1. 精俭排序；按照上述流程图应不难看出。

2. 稳定排序；合并过程中若两元素相等，前一序列的元素会被放在合并空间的前面。

3. 平均时间复杂度为O(nlogn)。

4. 空间复杂度为O(n)；在排序过程中申请了新的空间。

代码

    public static int[] mergeSort(int[] nums, int l, int h) {        if (l == h)            return new int[] { nums[l] };                 int mid = l + (h - l) / 2;        int[] leftArr = mergeSort(nums, l, mid); //左有序数组        int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组        int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组                 int m = 0, i = 0, j = 0;         while (i < leftArr.length && j < rightArr.length) {            newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];        }        while (i < leftArr.length)            newNum[m++] = leftArr[i++];        while (j < rightArr.length)            newNum[m++] = rightArr[j++];        return newNum;    }

以上是六种常见排序算法的总结。

原创不易，感谢关注！