3、排序

秒速五厘米 2022-05-27 04:11 49阅读 0赞

时间复杂度：程序运行耗费多少时间？  
空间复杂度：程序运行耗费了多少内存？

整理数据的第一步就是排序，即使已经存在许多标准的排序库，我们仍然需要学习排序算法。

## 基础排序 ##

### 冒泡排序 ###

![这里写图片描述][70]

public class BubbleSort {
    
        public static void main(String[] args) {
    
            int ayy[]= {
       5,6,7,1,2,3,4,9,8,10} ;
    
            for(int x =0 ;x< ayy.length ;x++){
                for(int y = x+1 ;y<ayy.length ;y++ ){ 
                    //每次子循环结束，就能找到该次循环的最小值，放在最前位置
                    if(ayy[x] > ayy[y]){
                        swap(ayy,x,y);
                    }
                }
            }
            System.out.println(Arrays.toString(ayy));
        }
    
        public static void swap(int ayy[],int x ,int y){
            int valY = ayy[y];
            ayy[y] = ayy[x] ;
            ayy[x] = valY ;
        }
    }

时间复杂度O(n²)

### 选择排序 ###

![这里写图片描述][70 1]  
选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

区别在于：冒泡算法，每次比较如果发现较小的元素在后面，就交换两个相邻的元素。而选择排序算法的改进在于：先并不急于调换位置，先从A\[1\]开始逐个检查，看哪个数最小就记下该数所在的位置P，等一躺扫描完毕，再把A\[P\]和A\[1\]对调，这时A\[1\]到A\[10\]中最小的数据就换到了最前面的位置。  
所以，选择排序每扫描一遍数组，只需要一次真正的交换，而冒泡可能需要很多次。比较的次数是一样的。  
![这里写图片描述][70 2]  
时间复杂度O(n²)

### 插入排序 ###

插入排序是一种简单直观的排序算法。它的工作原理非常类似于我们抓扑克牌，对于未排序数据(右手抓到的牌)，在已排序序列(左手已经排好序的手牌)中从后向前扫描，找到相应位置并插入。  
![这里写图片描述][70 3]

public class InsertSort {
        public static void main(String[] args) {
            int ayy[] = {
       5, 6, 7, 1, 2, 3, 4, 9, 8, 10};
            int insert;
            int j;
            //从第二元素开始 // i =3
            for (int i = 1; i < ayy.length; i++) {
                j = i;
                insert = ayy[i];
                while (j > 0 && insert < ayy[j - 1]) {
                    ayy[j] = ayy[j - 1];
                    j--;
    /* System.out.println(Arrays.toString(ayy)); System.out.println("j" + j);*/
                }
                ayy[j] = insert;
            }
            System.out.println(Arrays.toString(ayy));
        }
    }

时间复杂度O(n²)

## 高级排序 ##

### 希尔排序 ###

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如\[5,4,3,2,1,0\]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。

我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，\{n/2,(n/2)/2…1\}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

public static void sort(int[] arr) {
        //增量gap，并逐步缩小增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //从第gap个元素，逐个对其所在组进行直接插入排序操作
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        //移动法
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }
        }
    }

选择的增量序列\{n/2,(n/2)/2…1\}(希尔增量)，其最坏时间复杂度依然为O(n2)，一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n3/2)。

### 归并排序 ###

要将一个大的数组进行排序，可以先将他分为2个部分，然后递归的分为2个部分，直到最小部分为两个元素，对这两个元素进行排序；  
该算法会创建多个子数组；  
int\[\] temp = new int\[high - low + 1\];

public class MergeSort {   
        /** * 归并排序 * 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列 * 时间复杂度为O(nlogn) * 稳定排序方式 * @param nums 待排序数组 * @return 输出有序数组 */  
        public static int[] sort(int[] nums, int low, int high) {  
            int mid = (low + high) / 2;  
            if (low < high) {  
                // 左边 
                sort(nums, low, mid);  
                // 右边 
                sort(nums, mid + 1, high);  
                // 左右归并 
                merge(nums, low, mid, high);  
            }  
            return nums;  
        }  
    
        public static void merge(int[] nums, int low, int mid, int high) {  
            int[] temp = new int[high - low + 1];  
            int i = low;// 左指针 
            int j = mid + 1;// 右指针 
            int k = 0;  
    
            // 把较小的数先移到新数组中 
            while (i <= mid && j <= high) {  
                if (nums[i] < nums[j]) {  
                    temp[k++] = nums[i++];  
                } else {  
                    temp[k++] = nums[j++];  
                }  
            }  
    
            // 把左边剩余的数移入数组 
            while (i <= mid) {  
                temp[k++] = nums[i++];  
            }  
    
            // 把右边边剩余的数移入数组 
            while (j <= high) {  
                temp[k++] = nums[j++];  
            }  
    
            // 把新数组中的数覆盖nums数组 
            for (int k2 = 0; k2 < temp.length; k2++) {  
                nums[k2 + low] = temp[k2];  
            }  
        }  
    
        // 归并排序的实现 
        public static void main(String[] args) {  
            int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };  
            MergeSort.sort(nums, 0, nums.length-1);  
            System.out.println(Arrays.toString(nums));  
        }  
    }

![这里写图片描述][70 4]  
时间复杂度 O(nlogn)  
空间复杂度 O(n)  
![Center][]

### 快速排序 ###

快速排序也是一种分治的排序算法， 假设要排序的数组是A\[0\]……A\[N-1\]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：  
1、设置两个变量I、J，排序开始的时候I：=1，J：=N-1；  
2、以第一个数组元素作为关键数据，赋值给X，即X=A\[1\]；  
3、从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于X的值，两者交换；  
4、从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于X的值，两者交换；  
5、重复第3、4步，直到I=J；

public class QuickSort {   
        /** * 快速排序 */  
        public static void sort(int[] num, int left, int right) {  
            if (left < right) {  
                int dp = partition(num, left, right);  
                sort(num, left, dp - 1);  
                sort(num, dp + 1, right);  
            }  
        }  
    
        /** * 数据分组 */  
        public static int partition(int[] num, int left, int right) {  
            int pivot = num[left];  
            while (left < right) {  
                while (left < right && num[right] >= pivot)  
                    right--;  
                if (left < right)  
                    num[left++] = num[right];  
                while (left < right && num[left] <= pivot)  
                    left++;  
                if (left < right)  
                    num[right--] = num[left];  
            }  
            num[left] = pivot;  
            return left;  
        }  
    
        public static void main(String[] args) {  
            int[] num = { 1, 5, 3, 2 };  
            sort(num, 0, num.length - 1);  
            for (int i = 0; i < num.length; i++)  
                System.out.print(num[i] + " ");  
    
        }  
    
    }

![这里写图片描述][70 5]

排序方法 时间复杂度（平均） 时间复杂度（最坏) 时间复杂度（最好) 空间复杂度 稳定性 复杂性  
直接插入排序 O(n2) O(n2) O(n) O(1) 稳定 简单  
希尔排序 O(nlog2n) O(n2) O(n) O(1) 不稳定 较复杂  
直接选择排序 O(n2) O(n2) O(n2) O(1) 不稳定 简单  
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定 较复杂  
冒泡排序 O(n2) O(n2) O(n) O(1) 稳定 简单  
快速排序 O(nlog2n) O(n2) O(nlog2n) O(nlog2n) 不稳定 较复杂  
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定 较复杂  
基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(n+r) 稳定 较复杂

测试得出：  
当排序的数据量不大时，快排的速度大于归并排序，  
当排序的数据比较大时，归并排序的速度大于快排，

如果数据是基本有序的，那么归并更快一点不奇怪。也可能是cache的原因。要用性能热点分析工具才知道

[70]: /images/20220527/0fc6ef237f3b40dba1fb8a158da52637.png
[70 1]: /images/20220527/257e99dfb9f547aba4c041abae65641b.png
[70 2]: /images/20220527/00fdc61c64a744ebbd1f101b9eadf7f6.png
[70 3]: /images/20220527/8f35171c9f8b4f68817744e1c412ea0d.png
[70 4]: /images/20220527/06ce44842c764d28be8a50d08bc02789.png
[Center]: /images/20220527/a6bc6509cc4b4acbb02ff18f8c2050b6.png
[70 5]: /images/20220527/f497a24064984a54b375262940eaf35f.png