算法 - 常见的排序算法总结

介绍

查了一下维基百科，发现排序算法有这么多种，但是大多数都是不常用的，所以今天就来总结一下我们常用到的排序算法。

在计算机科学与数学中，一个排序算法（英语：Sorting algorithm）是一种能将一串数据依照特定排序方式进行排列的一种算法。最常用到的排序方式是数值顺序以及字典顺序。有效的排序算法在一些算法（例如搜索算法与合并算法）中是重要的，如此这些算法才能得到正确解答。排序算法也用在处理文字数据以及产生人类可读的输出结果。基本上，排序算法的输出必须遵守下列两个原则：
1.输出结果为递增序列（递增是针对所需的排序顺序而言）。
2.输出结果是原输入的一种排列、或是重组。

刚好刷到 912. Sort an Array 一题，借由这个机会，总结一下数据结构与算法课程刚好讲到的各种排序算法。各种排序算法主要可以通过时间复杂度、是否稳定、是否利用附加存储来评价。

• 时间复杂度： O(nlogn)``O(n^2)``O(n+k)``O(n*k)
• 内存使用量：在原地址上进行操作，还是需要额外的内存空间。
• 稳定性：指相同大小的元素在排序后相对位置不会发生改变。
• 依据排序的方式：插入、交换、选择、合并。

直接插入排序：

（有序区，无序区）。把无序区的第一个元素插入到有序区的合适的位置。对数组：比较得少，换得多。

首先，它是一种插入排序。

每次插入到已经排好序的子序列中，使得数组逐渐有序。

时间复杂度 O(n^2)，空间复杂度 O(1)，是稳定的排序算法，因为我们我们寻找的是有序子序列中第一个大于当前元素的元素的下标。相等元素的相对位置不会发生改变。

/*直接插入排序*/
public void insertSort(int[] nums) {
    for(int i=1; i<nums.length; i++) {
        int flag=i, tmp=nums[i];    //插入的下标位置、当前元素的副本
        for(int j=0; j<i; j++) {
            if(nums[i]<nums[j]) {flag=j; break;}    //找到插入位置
        }
        for(int j=i; j>flag; j--) {
            nums[j]=nums[j-1];  //插入位置之后的元素顺移
        }
        nums[flag]=tmp; //插入元素
    }
}

折半插入排序：

插入排序的优化版。

在直接插入排序上降低了查找应该插入下标位置的平均时间。采用的是二分查找。

时间复杂度仍然是 O(n^2) 因为移动元素必然要花费 O(n) 的时间，只是相对于直接插入排序性能稍微有所提升。

/*折半插入排序*/
public void binaryInsertSort(int[] nums) {
    for(int i=1; i<nums.length; i++) {
        int tmp=nums[i];    
        int low=0, high=i-1, mid=-1;
        while(low<=high) {
            mid=(low+high)/2;
            if(nums[mid]>tmp) high=mid-1;
            else low=mid+1;
        }
        for(int j=i; j>low; j--) {
            nums[j]=nums[j-1];  //插入位置之后的元素顺移
        }
        nums[low]=tmp; //插入元素 
    }
} 

希尔排序：

每一轮按照事先决定的间隔进行插入排序，间隔会依次缩小，最后一次一定要是 1。

首先，它是一种插入排序，是插入排序的升级版，也叫做缩小增量排序。

就是按照增量对数组进行划分，划分成几个子数组，在子数组中进行插入排序，一趟下俩，实现宏观有序。再缩小增量，再对数组进行划分，划分成几个子数组（注意这个时候数组个数更小了），再对子数组进行插入排序。当增量为 1 时，数组基本有序，做个简单的插入排序就 ok。希尔排序的实质上是通过减少插入排序需要移动的次数，来降低时间复杂度。

时间复杂度 O(n^1.3) 空间复杂度 O(1)

一般选取增量 step/=2

/*希尔排序*/
public void shellSort(int[] nums) {
    for(int step=nums.length/2; step>0; step/=2) {
        for(int i=step; i<nums.length; i++) {   //骨子里还是插入排序
            int j=i, tmp=nums[i];
            while(j-step>=0 && nums[j-step]>tmp) {  //后移大于tmp的元素，找到tmp插入点
                nums[j]=nums[j-step];
                j-=step;
            }
            nums[j]=tmp; 
        }
    }
} 

简单选择排序：

（有序区，无序区）。在无序区里找一个最小的元素跟在有序区的后面。对数组：比较得多，换得少。

首先，它是一种选择排序。

每次选择出后缀序列的最小值放到其正确位置，使得数组逐渐有序

间复杂度 O(n^2)，空间复杂度 O(1)，是不稳定的排序算法，因为我们找后缀序列的最小值和当前位置的元素值相等时，我们交换了它们的相对位置，破坏了排序的稳定性。

/*简单选择排序*/
public void selectSort(int[] nums) {
    for(int i=0; i<nums.length-1; i++) {
        int min=i, tmp=nums[i];
        for(int j=i+1; j<nums.length; j++) {
            if(nums[j]<nums[min]) {min=j; }
        }
        if(min!=i) {nums[i]=nums[min]; nums[min]=tmp; } //swap
    }
}

堆排序：

（最大堆，有序区）。从堆顶把根卸出来放在有序区之前，再恢复堆。

首先，它是一种选择排序，是简单选择排序的升级版。

利用最大堆来不断寻找前缀序列的最大值，把它放置在正确位置上，使得数组主键有序。

先将数组维护成最大堆的形式，再交换堆的最大值和堆的末尾值，即：交换 A[0] 和 A[j]，使得前序的最大值处于数组的正确位置，迭代 j 使其 n-1 to 1.

时间复杂度 O(nlogn)，时间主要用在建立最大堆上，空间复杂度 O(1)，是不稳定的排序算法。因为相等元素大概率不位于一条路径(从堆顶到堆底)，即相等元素可能不会比较到，所以相对位置可能会改变。

/*堆排序*/
public void heapSort(int[] nums) {
    int n=nums.length;
    for(int i=n/2; i>=0; i--) { //建立最大堆
        adjustHeap(nums, i, n);
    }
    for(int j=n-1; j>=1; j--) {
        int max=nums[0];
        nums[0]=nums[j]; nums[j]=max; //交换,使得最大值处于正确位置
        n--;
        adjustHeap(nums, 0, n);  //调整堆
    }
}
public void adjustHeap(int[] nums, int i, int heapSize) {
    int left=2*i+1, right=2*(i+1), maxIndex=i;

    if(left<heapSize  && nums[left]>nums[i]) maxIndex=left;
    if(right<heapSize && nums[right]>nums[maxIndex]) maxIndex=right;

    if(maxIndex!=i) {   
        int max=nums[maxIndex];  
        nums[maxIndex]=nums[i]; nums[i]=max;  //交换
        adjustHeap(nums, maxIndex, heapSize);   //调整子堆
    }
}

冒泡排序：

（无序区，有序区）。从无序区透过交换找出最大元素放到有序区前端。

首先，它是一种交换排序。

每次通过交换一个逆序对，使得数组逐渐有序。

进行 n 轮冒泡，每轮两两比较将较大的值推送到其正确位置，平均时间复杂度 O(n^2)，空间复杂度 O(1)，是稳定的排序算法，因为我们只交换逆序对，当元素相等时，不交换其相对位置。

/*冒泡排序*/
public void bubble(int[] nums) {
    for(int i=0; i<nums.length; i++) {    //冒泡轮数
        for(int j=0; j<nums.length-i-1; j++) {
            if(nums[j]>nums[j+1]) {
                int tmp=nums[j]; nums[j]=nums[j+1]; nums[j+1]=tmp;  //两两交换
            }
        }
    }
}

快速排序

（小数，基准元素，大数）。在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。

首先，它是一种交换排序，是冒泡排序的升级版。

每次划分，找到一个支点，支点左边全是小于支点的元素（左序列），支点右边全是大于支点的元素（右序列），然后递归划分这两个子序列。

时间复杂度是 O(nlogn) 空间复杂度是 O(logn) 内存空间主要花费在创建递归过程上。

是不稳定的排序算法，因为交换一个逆序对可能会改变相等元素的位置。

/*快速排序*/
public void quickSort(int[] nums) {
    partition(nums, 0, nums.length-1);
}
public void partition(int[] nums, int start, int end) {
    if(start>=end) return;  //终止条件

    int pivot=nums[(start+end)/2]; //基准
    int l=start, r=end; //左右指针
    while(l<=r) {
        while(nums[l]<pivot) {l++; }    //找到比支点大的数
        while(nums[r]>pivot) {r--; }    //找到比支点小的数
        if(l<=r) {      //交换
            int tmp=nums[l];
            nums[l]=nums[r];
            nums[r]=tmp;
            l++; r--;   //避免相等元素无限交换，进入死循环
        }
    }
    partition(nums, start, r);
    partition(nums, l, end);
}

归并排序：

把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。

将序列逐层分解，直到子序列中只有一个元素(必然有序)，再不断向上合并，就是让两个有序子序列合并成一个有序子序列的过程，合并到最顶层的时候，序列必然有序。

整个过程采用递归的方式完成。

总结一下，就是：先分解成两个子序列，两个子序列调用递归方法，完成有序，再合并两个有序子序列。

时间复杂度为 O(nlogn) 空间复杂度为 O(n)，因为每次合并都要创建两个数组保存副本。(其实可以只创建一个副本数组)，是稳定的排序算法，因为合并过程中：你可以选择使得相等元素保持原有顺序.

/*归并排序*/
public void mergeSort(int[] nums) {
    merge(nums, 0, nums.length-1);
}
public void merge(int[] nums, int start, int end) {
    if(start==end)  return;
    //分解
    int middle=(start+end)/2;
    merge(nums, start, middle);
    merge(nums, middle+1, end);
    //合并
    int[] l=new int[middle-start+1], r=new int[end-middle];
    for(int i=start; i<=middle; i++) {l[i-start]=nums[i]; }
    for(int i=middle+1; i<=end; i++) {r[i-(middle+1)]=nums[i]; }
    int m=0, n=0;
    for(int i=start; i<=end; i++) {
        if((m<l.length && n<r.length && l[m]<=r[n]) || n==r.length) {
            nums[i]=l[m]; m++;
        }else if((m<l.length && n<r.length && l[m]>r[n]) || m==l.length) {
            nums[i]=r[n]; n++;
        }
    }
}

总结：

排序算法实质上就是消除数组中逆序对的个数。一个随机数组有 O(n^2) 个逆序对。如果采用**“交换相邻元素”**的办法来消除逆序，每次正好只消除一个，因此必须执行 O(n^2) 的交换次数，这就是为啥冒泡、插入等算法只能到平方级别的原因，反过来，基于交换元素的排序要想突破这个下界，必须执行一些比较，交换相隔比较远的元素，使得一次交换能消除一个以上的逆序，希尔、快排、堆排等等算法都是交换比较远的元素，只不过规则各不同罢了。

• 均按从小到大排列
• k 代表数值中的"数字"个数
• n 代表数据规模
• m 代表数据的最大值减最小值