数据结构——八大排序算法（面试/数据结构期末考试-简单且详细）

r囧r小猫 2024-04-03 14:18 82阅读 0赞

**目录**

1.直接插入排序

1.1 代码实现

1.2 复杂度

2.希尔排序

2.1 代码实现

2.2 复杂度

3.选择排序

3.1 代码实现

3.2 复杂度

4.堆排序

4.1 代码实现

4.2 复杂度

5.冒泡排序

5.1 代码实现

5.2 复杂度1

5.3 优化后的代码实现

5.4 复杂度2

6.快速排序

6.1 代码实现

6.2 复杂度

7.归并排序

7.1 代码实现

7.2 归并排序的递归实现

7.3 复杂度

7.4 归并排序的非递归实现

8.非比较排序

基数排序

--------------------

## 1.直接插入排序 ##

对于一组数据，直接插入排序，认为第一位有序，将后面的数据与第一位比较，小于第一位数据则排在第一位数据的前面，大于则不动。

例如：有如下15个数据

定义一个tmp作为中间变量。由于认为第一位有序，则定义i从第二位开始，并定义j为第一位的下标，用于比较。如下图

![7902a75c0e104b079868b9127e0360e1.png][]

比较i下标与j下标值的大小，发现有序，则i++

> 发现有序，则
> 
> i++
> 
> j = i -1

![e50d80a52b2b41af971f055627f05159.png][]

> 先 tmp = array\[i\]

如下图

![056e3cdce10d48b1bca72c8151da14da.png][]

> 发现array\[j\] > tmp,则
> 
> array\[j+1\] = array\[j\];
> 
> j--；

如下图

![490726b1397248a5a5e880a586a6cb35.png][]

> 发现array\[j\] > tmp, 则
> 
> array\[j+1\] = array\[j\];
> 
> j--；

如下图

![d7ac5ab9b99c43578f72be60e45be5d0.png][]

> 此时j < 0,则
> 
> array\[j+1\] = tmp；
> 
> i++;
> 
> j = i - 1;

如下图

![878f90a0018d47428eafb18076aca09e.png][]

这样就实现了j下标之前的数据完成了有序。

往复如此，就可以实现整个数组的有序。

### 1.1 代码实现 ###

public static void insertSort(int[] array){
            for (int i = 1; i < array.length; i++) {
                int j = i - 1;
                int tmp = array[i];
                for (; j >= 0; j--) {
                    if(array[j] > tmp){
                        array[j+1] = array[j];
    
                    }else{
                        //array[j+1] = tmp;
                        break;
                    }
                }
                array[j+1] = tmp;
            }
        }

### 1.2 复杂度 ###

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性:稳定

## 2.希尔排序 ##

希尔排序又称为缩小增量排序

希尔排序是对直接插入排序的优化，利用分组的思想，每组进行直接插入排序，有效降低时间复杂度。

例如：有如下15个数据

按正常人思维，应该是按顺序分组

第一次分组：分5组

组别1：12 23 4 排序后：4 12 23

组别2：0 22 38 排序后：0 22 38

组别3：98 55 50 排序后：50 55 98

组别4：78 45 66 排序后：45 66 78

组别5：49 37 20 排序后：20 37 49

分组并排序后，此时数据如下

第二次分组：分3组：

组别1：4 12 23 0 22 排序后：0 4 12 22 23

组别2：38 50 55 98 45 排序后：38 45 50 55 98

组别3：66 78 20 37 49 排序后：20 37 49 66 78

第三次分组：分一组，并进行直接插入排序。

最后一定是分成一组，之前的分组都是预分组。

注意，为什么是5 ，3 ，1分组？而不是5 4 1等其他的分组？这涉及希尔排序的缩小增量的方法。

**希尔排序的分析是一个复杂的问题，因为它的时间是所取“增量”的函数，这涉及一些数学上的尚未解决的难题。因此，到目前为止尚未有人求的一种最好的增量序列，但大量的研究得到了一些局部的结论。增量序列有多种取法，但需注意：应使增量序列中的值没有除1之外的公因子（素数），且最后一个增量值必须为1。**

一般认为希尔排序的分组如下所示，每个颜色对应一组，共5组，并对每一组进行直接插入排序

![680b682449434225ae7a971832fd60b1.png][]

由于是分5组，我们令gap = 5，i与j始终相差5，从第一组开始进行排序，排序后令i++。

这种分组方法相比于前面说的按顺序分组的方法，大概率将小的数据放在前面，大的数据放在后面，使得这组数据更加有序。

### 2.1 代码实现 ###

经上面分析，希尔排序最重要的一点就是如何分组。

写出shell()函数进行排序，shell()函数本质上就是直接插入排序。

shellSort()函数进行分组。令gap等于array数组的长度，总而进行排序，每次分组都是gap /= 2。以上都是预排序，注意最后一定要令gap = 1进行排序。

代码如下：

public static void shell(int[] array,int gap){
            for(int i = gap;i < array.length;i++){
                int tmp = array[i];
                int j = i - gap;
                for(;j >= 0;j -= gap){
                    if(array[j] > tmp){
                        array[j + gap] = array[j];
                    }else {
                        break;
                    }
                }
                array[j + gap] = tmp;
            }
        }
        public static void shellSort(int[] array){
            int gap = array.length;
            while(gap > 1){
                shell(array,gap);
                gap /= 2;
            }
            shell(array,1);
        }

代码“gap /= 2”保证了每次增量都是缩小的，目前来说无法保证每次都是素数。

### 2.2 复杂度 ###

时间复杂度：和它的增量有关 。为O(n^1.3--n^1.5)

空间复杂度：O(1)

稳定性:不稳定

**由于对于直接插入排序来说，数据越有序越快，所以它经常用于排序的优化上**

## 3.选择排序 ##

对于一组数据，i指向第一个元素，j指向i下一个元素，判断i下标的元素与j下标元素大小，若i下标元素大于j下标元素，则交换它们。j++走完后得出i下标后面的最小元素并完成了交换，此时i++，直至i走完整个数组。

### 3.1 代码实现 ###

public static void selectSort(int[] array){
            for (int i = 0; i < array.length; i++) {
                for (int j = i + 1; j < array.length; j++) {
                    if(array[i] > array[j]){
                        int tmp = array[i];
                        array[i] = array[j];
                        array[j] = tmp;
                    }
                }
            }
        }

### 3.2 复杂度 ###

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

## 4.堆排序 ##

基本原理是选择排序，**排升序建立大堆，排降序建立小堆**。

首先我们创建大根堆，令child = array.length - 1，则child的父节点是parent = (rray.length - 1 - 1)/2,

### 4.1 代码实现 ###

public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void heapSort(int[] array){
            createHeap(array);
            int end = array.length - 1;
            while(end > 0){
                swap(array,0,end);
                shiftDown(0,end,array);
                end--;
            }
        }
        public static void createHeap(int[] array){
            for(int parent = (array.length - 1 - 1) / 2;parent >= 0;parent--){
                shiftDown(parent,array.length,array);
            }
        }
        public static void shiftDown(int parent,int len,int[] array){
            int child = 2*parent+1;
            while(child < len){
                if(child + 1 < len &&array[child] < array[child+1]){
                    child++;
                }
    
                if(array[child] > array[parent]){
                    swap((array,child,parent);
                    parent = child;
                    child = 2*parent+1;
                }else {
                    break;
                }
            }
        }

### 4.2 复杂度 ###

时间复杂度：O(N\*log(2)(N))

空间复杂度：O(1)

稳定性：不稳定

## 5.冒泡排序 ##

例如：有如下15个数据

定义一个j，从0下标开始，从左往右依次比较排序，直至本次j走完数组，然后在此基础上再次从左往右依次比较排序，直到结束。

### 5.1 代码实现 ###

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

### 5.2 复杂度1 ###

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性：稳定

注意：冒泡排序可以优化从而减小时间复杂度；例如每次j走完后，后面的元素就会有序，不用再进行排序，又例如，当某一次j走完后数据已经完成了有序，就不用再进行排序。

### 5.3 优化后的代码实现 ###

public static void bubbleSort2(int[] array){
            for (int i = 0; i < array.length-1; i++) {
                boolean flag = false;
                for (int j = 0; j < array.length-1-i; j++) {
                    if(array[j] > array[j+1]){
                        int t = array[j];
                        array[j] = array[j+1];
                        array[j+1] = t;
                        flag = true;
                    }
                }
                if(flag == false){
                    break;
                }
    
            }
        }

### 5.4 复杂度2 ###

时间复杂度：最坏情况O(N^2)。最好情况O(N)

空间复杂度：O(1)

稳定性：稳定

## 6.快速排序 ##

从待排序的数据中选择一个数据作为**基准**（pivot），遍历待排序的数据，小于基准值的放在左边，大于基准值的放在右边，对左右两边用同样的方法继续处理，直至最小区间长度为1。

例如：有如下15个数据

对于基准（pivot）的寻找，可以用以下方法：

定义start为0下标，定义end为最后一个的下标，并定义tmp作为中间变量。

![11dbf4b1515d47f4a5d9c2513a1a2e56.png][]

令tmp = array\[start\]

![14aff2975830425f9c9e3ee5fbb3da28.png][]

从后面开始，判断end下标数据是否大于tmp中的值，若array\[end\] > tmp,则end--;若array\[end\] < tmp,则array\[start\] = array\[end\],然后start++，判断start下标数据是否小于tmp中的值，若array\[start\] < tmp，则start++，若array\[start\] > tmp,则array\[end\] = array\[start\],然后end--，再进行end下标的判断，直至end = start，此时定义一个pivot = tmp = array\[start\] = array\[end\]。

可以利用**递归**的方法，如此反复，直至序列有序。

### 6.1 代码实现 ###

//排序
        public static void quickSort(int[] array,int left,int right){
            if(left >= right) return;
            int pivot = partition(array,left,right);//基准
            quickSort(array,left,pivot-1);
            quickSort(array,pivot+1,right);
        }
        //寻找基准
        private static int partition(int[] array,int start,int end){
            int tmp = array[start];
            while(start < end) {
                while(start < end && array[end] >= tmp) end--;
                array[start] = array[end];
                while(start < end && array[start] <= tmp) start++;
                array[end] = array[start];
            }
            int pivot = array[end] = tmp;
            return start;
        }

### 6.2 复杂度 ###

时间复杂度：最好情况O(N\*log(2)(N))，最坏情况：O(N^2)

空间复杂度：最好情况O(log(2)(N))，最坏情况：O(N)

稳定性：不稳定

## 7.归并排序 ##

*所谓归并排序是指将两个或两个以上有序的数列(或有序表),合并成一个仍然有序的数列(或有序表)*

如以下两个序列![9c8495a490494904af177206d82a37a3.png][]

排序后

![29e89bee189142f3ac5644244d574813.png][]

对于归并排序，可以给array1定义一个start1，给array2定义start2，都从序列的首位开始，遍历序列，每次遇到更大的数就给新的array，直至两个待归并的排序列遍历结束。

### 7.1 代码实现 ###

public static int[] mergeArray(int[] array1,int[] array2){
            int start1 = 0;
            int start2 = 0;
            int x = 0;
            int[] array = new int[array1.length + array2.length];
            while(start1 <= array1.length - 1 && start2 <= array2.length - 1){
                if(array1[start1] < array2[start2]){
                    array[x] = array1[start1];
                    x++;
                    start1++;
                }else {
                    array[x] = array2[start2];
                    x++;
                    start2++;
                }
            }
            while(start1 <= array1.length - 1 ){
                array[x] = array2[start1];
                x++;
                start1++;
            }
            while(start2 <= array2.length - 1){
                array[x] = array2[start2];
                x++;
                start2++;
            }
            return array;
        }

### 7.2 归并排序的递归实现 ###

public static void mergeSort(int[] array){
            mergeSortInternal(array,0,array.length-1);
    
        }
        private static void mergeSortInternal(int[] array,int low,int high){
    
            if(low >= high){
                return;
            }
    
            //int mid = (low+high) >>> 1;//也可以写作
            int mid = low + ((high - low)>>> 1);
    
            mergeSortInternal(array,low,mid);//左
            mergeSortInternal(array,mid+1,high);//右
    
            merge(array,low,mid,high);
    
        }
    
        private static void merge(int[] array,int low,int mid,int high){
            int[] tmp = new int[high-low+1];
            int x = 0;
    
            int start1 = low;
            int end1 = mid;
            int start2 = mid + 1;
            int end2 = high;
    
            while(start1 <= end1 && start2 <= end2){
                if(array[start1] < array[start2]){
                    tmp[x] = array[start1];
                    x++;
                    start1++;
                }else {
                    tmp[x] = array[start2];
                    x++;
                    start2++;
                }
            }
            while(start1 <= end1){
                tmp[x] = array[start1];
                x++;
                start1++;
            }
            while(start2 <= end2){
                tmp[x] = array[start2];
                x++;
                start2++;
            }
            for (int i = 0; i < x; i++) {
                array[low+i] = tmp[i];
    
            }
    
        }

### 7.3 复杂度 ###

时间复杂度：O(N\*log(2)(N))

空间复杂度：O(N)

稳定性：不稳定

### 7.4 归并排序的非递归实现 ###

private static void merge(int[] array,int low,int mid,int high){
            int[] tmp = new int[high-low+1];
            int x = 0;
    
            int start1 = low;
            int end1 = mid;
            int start2 = mid + 1;
            int end2 = high;
    
            while(start1 <= end1 && start2 <= end2){
                if(array[start1] < array[start2]){
                    tmp[x] = array[start1];
                    x++;
                    start1++;
                }else {
                    tmp[x] = array[start2];
                    x++;
                    start2++;
                }
            }
            while(start1 <= end1){
                tmp[x] = array[start1];
                x++;
                start1++;
            }
            while(start2 <= end2){
                tmp[x] = array[start2];
                x++;
                start2++;
            }
            for (int i = 0; i < x; i++) {
                array[low+i] = tmp[i];
    
            }
    
        }
    
    
        public static void mergeSort(int[] array){
            int nums = 1;
    
            while(nums < array.length){
                for (int i = 0; i < array.length; i += 2*nums) {
                    int left = i;
                    int mid = left + nums - 1;
                    if(mid >= array.length){
                        mid = array.length - 1;
                    }
                    int right = mid + nums;
                    if(right >= array.length){
                        right = array.length - 1;
                    }
                    merge(array,left,mid,right);
                }
                nums *= 2;
    
            }
        }

## 8.非比较排序 ##

### 基数排序 ###

例如：有以下数据：12，245，78，119，656，38，500

假设有十个桶（可想象成队列），从0开始依次排序。（由于是十进制，所以是十个桶）

如下图：

![f0e0235905ec4651a490e791620a7c1d.png][]

根据每个数的个位数，遍历数组12，245，78，119，656，38，500，依次进入个位数对应的“桶”

如下图

![d9505e08cd3446bfbe81c3544f3d9b86.png][]

再从0桶开始依次出桶（根据队列的方式出桶） 如下图

![7155733c4d3440bc9685e357cbffc11d.png][]

根据每个数的十位数，遍历数组500，12，245，656，78，38，119，依次进入十位数对应的“桶”

如下图

![ff91616c443a4bcc9c9d633e944e844a.png][]

再从0桶开始依次出桶（根据队列的方式出桶）如下图

![ae7180b261794a989cc1ecf03801bcb2.png][]

根据每个数的百位数，遍历数组500，12，119，38，245，656，78依次进入百位数对应的“桶”

如下图

![e6434d6b4d9f41b08ab48cc206cef43e.png][]

再从0桶开始依次出桶（根据队列的方式出桶）如下图

![64db59f681fc4931b07282734a10d6e3.png][] 最后得到12，38，78，119，245，500，656这个有序的序列。

**基数排序仅作了解，面试基本不会考到。**

[7902a75c0e104b079868b9127e0360e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/8e459468fd5c4a83853d08629293dcab.png
[e50d80a52b2b41af971f055627f05159.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/d01759f0681e43cfbe18b032fad66940.png
[056e3cdce10d48b1bca72c8151da14da.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b84611447a10424a85de2fb1d2bf5392.png
[490726b1397248a5a5e880a586a6cb35.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/ee37da5f148f46f9bf07161c8052a376.png
[d7ac5ab9b99c43578f72be60e45be5d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/23ea964e8ddb4175809bde0f97d48bb3.png
[878f90a0018d47428eafb18076aca09e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/d1be12a8557442e7853401bdd23bd931.png
[680b682449434225ae7a971832fd60b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/9952220f0e6f4e8db25df4c97cc933c1.png
[11dbf4b1515d47f4a5d9c2513a1a2e56.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/a8a553aef3964aaaa21fa05eb266634e.png
[14aff2975830425f9c9e3ee5fbb3da28.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/67328da8af764b8ea053707147c47a69.png
[9c8495a490494904af177206d82a37a3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/074802c9a35942419ad36c63250ffa4c.png
[29e89bee189142f3ac5644244d574813.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/32529d3f32674005ad7af0f3e57f2ea4.png
[f0e0235905ec4651a490e791620a7c1d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/189864af77ed41ddada99e91a5fd2c98.png
[d9505e08cd3446bfbe81c3544f3d9b86.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f1dd3a251c624cd5a4cced9d0460fe37.png
[7155733c4d3440bc9685e357cbffc11d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/e426b6f05a7d4607948fe4140f728547.png
[ff91616c443a4bcc9c9d633e944e844a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/8416650fc94b4702be70e87acc3881d9.png
[ae7180b261794a989cc1ecf03801bcb2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/8eeb6dd0dedd43e696312606a233e72d.png
[e6434d6b4d9f41b08ab48cc206cef43e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/9225c0d53d08417ba2ea30a65489e32a.png
[64db59f681fc4931b07282734a10d6e3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/8b8419231c65485db9d12c96d40783f6.png