273973-19cf4a1e58b6ebaf.png paixu.jpg

• 排序稳定性
  首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前。
  其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些（个人感觉，没有证实）。

回到主题，现在分析一下常见的排序算法的稳定性，每个都给出简单的理由。

(1)冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

(2)选择排序

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n - 1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

(3)插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

(4)快速排序
快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j，交换a[i]和a[j],重复上面的过程，直到i > j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。

(5)归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

(6)基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。

(7)希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

(8)堆排序
我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1， n / 2 - 2， ... 1这些个父节点选择元素时，就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。

冒泡排序

/**
 * 冒泡排序
*/
class Solution{
public:
    void sort(vector<int> &nums){
        int mark=1;
        int size=nums.size();
        while(mark !=0 ){
            mark=0;
            for(int i=0;i<size-1;i++){
                if(nums[i]>nums[i+1]){
                   swap(nums[i],nums[i+1])
                    mark++;
                }
            }
        }
    }
};

选择排序

/**
 * 选择排序
*/
class Solution{
public:
    void sort(vector<int> &nums){
        int size=nums.size();
        for(int i=0;i<size-1;i++){
            int temp=i;
            for(int j=i+1;j<size;j++){
                if(nums[temp] > nums[j])
                    temp=j;
            }
            swap(nums[temp],nums[i])
        }
    }
};

普通插入排序

• 算法原理
  将数据分为两部分，有序部分与无序部分，一开始有序部分包含第1个元素，依次将无序的元素插入到有序部分，直到所有元素有序。插入排序又分为直接插入排序、二分插入排序、链表插入等，这里只讨论直接插入排序。它是稳定的排序算法，时间复杂度为O(n^2)
• 时间复杂度
  在最好的情况下（元素已经排好顺序）：那么只需要循环 n-1 次就可以了，时间复杂度 O（n）
  在最差的情况下 （元素是逆序的）：要循环调整次数： [ n * (n-1) ] / 2 ，时间复杂度为 O（n ^ 2）
  平均时间复杂度为：O（n ^ 2）

/**
 * 普通插入排序
*/

class Solution{
public:
    void sort(vector<int> &nums){
        cout << " 普通法插入 " <<endl;
        int size=nums.size();
        for(int i=1;i<size;i++){
            for(int j=i;j>0;j--){
                if(nums[j-1]>nums[j]){
                    swap(nums[j-1],nums[j]);
                }
                else break;
            }
        }
    }
private:
};

二分法插入排序

• 算法原理
  折半插入排序的基本思想与直接插入排序一样，在插入第i(i≥1)i(i≥1)个元素时，前面i−1i−1个元素已经排好序。区别在于寻找插入位置的方法不同，折半插入排序是采用折半查找法来寻找插入位置的。
  折半查找法的基本思路是：用待插元素的值与当前查找序列的中间元素的值进行比较，以当前查找序列的中间元素为分界，确定待插元素是在当前查找序列的左边还是右边，如果是在其左边，则以该左边序列为当前查找序列，右边也类似。按照上述方法，递归地处理新序列，直到当前查找序列的长度小于1时查找过程结束。
• 时间复杂度
  折半插入排序适合记录数较多的场景，与直接插入排序相比，折半插入排序在寻找插入位置上面所花的时间大大减少，但是折半插入排序在记录移动次数方面和直接插入排序是一样的，所以其时间复杂度为O(n2)。
  其次，折半插入排序的记录比较次数与初始序列无关。因为每趟排序折半寻找插入位置时，折半次数是一定的，折半一次就要比较一次，所以比较次数也是一定的。
  稳定排序

/**
 * 二分法插入排序
 * 
 * 考虑边界
*/
class Solution{
public:
    void sort(vector<int> &nums){
        cout << " 二分法插入 " <<endl;
        int size=nums.size();
        vector<int> ret;
        ret.push_back(nums[0]);
        for(int i=1;i<size;i++){
            sortinsert(ret,nums[i]);
        }
        nums.swap(ret);
    }
private:
    void sortinsert(vector<int> &nums,int a){
        int size=nums.size();
        if((a>=nums[size-1])){
            nums.push_back(a);
            return;
        }
        else if((a<=nums[0])){
            nums.insert(nums.begin(),a);
            return;
        }
        int l=0;
        int r=size-1;
        int mid=0;
        while(l<r){
            mid=l+(r-l)/2;
            if( nums[mid] < a){
                if(a< nums[mid+1]){
                    mid=mid+1;
                    break;
                    }
                else{
                    l=mid+1;
                }
            }
            else if(a < nums[mid]){
                if(nums[mid-1] < a){
                    // mid = mid-1; 
                    break;
                }
                else{
                    r=mid-1;
                }
            }
            else{
                break;
            }
        }
        auto beg=nums.begin();
        beg+=mid;
        nums.insert(beg,a);
        return;
    }
};

最后必须取low位置为插入点，因为low之前的数字全部小于或等于插入值。

二分插入排序 
public void BinaryInsertSort(int[] a, int left, int right) {
    int low, middle, high;
        int temp;
    for (int i = left + 1; i <= right; i++) {
            temp = a[i];
            low = left;
            high = i - 1;
            while (low <= high) {
                middle = (low + high) / 2;
                if (a[i] < a[middle])
                    high = middle - 1;
                else
                    low = middle + 1;
        }

            for (int j = i - 1; j >= low; j--)
                    a[j + 1] = a[j];

            a[low] = temp;
        }

希尔排序

• 算法原理
  将无序数组分割为若干个子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，对各个子序列进行插入排序；然后再选择一个更小的增量，再将数组分割为多个子序列进行排序......最后选择增量为1，即使用直接插入排序，使最终数组成为有序。
• 增量的选择：
  在每趟的排序过程都有一个增量，至少满足一个规则 增量关系 d[1] > d[2] > d[3] >..> d[t] = 1 (t趟排序)；根据增量序列的选取其时间复杂度也会有变化，这个不少论文进行了研究，在此处就不再深究；本文采用首选增量为n/2,以此递推，每次增量为原先的1/2，直到增量为1；

xier.jpg xier2.jpg

/**
 * 希尔排序
*/
class Solution
{
  public:
    void sort(vector<int> &nums)
    {
        cout << " 希尔排序 " << endl;
        int size = nums.size();
        int interval = size;
        int mult = 2;
        while (1)
        { //loop times
            interval = size / mult;
            for (int i = 0; i < interval; i++)
            {
                for (int j = i + interval; j < size; j += interval)
                {
                    for (int k = j; k >= interval; k -= interval)
                    {
                        if (nums[k - interval] > nums[k])
                        {
                            int temp = nums[k];
                            nums[k] = nums[k - interval];
                            nums[k - interval] = temp;
                        }
                        else
                        {
                            break;
                        }
                    }
                }
            }
            mult *= 2;
            if (interval == 1)
                return;
        }
    }
};

/**
 * 希尔排序
*/
class Solution
{
    public:
    void sort(vector<int> &nums)
    {
        for (int gap = nums.size() >> 1; gap > 0; gap >>= 1)
        { // times
            for (int i = gap; i < nums.size(); i++)
            { 
                for (int j=i; j >gap-1;  j -= gap)
                {
                   if(nums[j-gap]>nums[j])
                      swap(nums[j-gap],nums[j])
                   else break;
                }
            }
        }
    }
};

快速排序

• 算法原理
  快速排序是目前在实践中非常高效的一种排序算法，它不是稳定的排序算法，平均时间复杂度为O(nlogn)，最差情况下复杂度为O(n^2)。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

• 平均时间复杂度 nlogN
  n个数字，每次分成两份，一共要分logn次，每一次排序要操作n次。所以平均时间复杂度为 nlogn。

• 最差事件复杂度 n^2
  最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)
  这种情况时间复杂度就好计算了，就是冒泡排序的时间复杂度：T[n] = n * (n-1) = n^2 + n;
  综上所述：快速排序最差的情况下时间复杂度为：O( n^2 )

/**
 * 快速排序
 * 基准数字的位置与先从右边开始找还从左边开始找是有联系的。
 * 若基准数字在左边，则应该先从右边开始找，这样找到的最后位置肯定是
 * 数值比基准数字小。
 * 若从左边开始找，则找到的最后位置肯定是数值比基准数字大。
*/

另一组实现，从头开始遍历，标准值为A，维护两个pos,pos1表示当前比较的数据位置，pos2表示当前最靠前的一个大于A的数字的位置。如果pos1的数值小于A，则交换pos1和pos2的数值。然后pos1++,pos++。否则只有pos1++。
也就是说pos2之前的数字都是小于A的，pos2到pos1之间的数字都是大于等于A。

class Solution
{
  public:
    void sort(vector<int> &nums)
    {
            cout << " 快速排序 " << endl;
        quick_sort(nums,0,nums.size()-1);
    }
  private:
    void quick_sort(vector<int> &nums, int cl, int cr)
    {
        int l = cl;
        int r = cr;
        int mark = l;
        if (l < r)
        {
            while (l < r)
            {
                while (nums[r] >= nums[mark] && l < r)
                    r--;
                while (nums[l] <= nums[mark] && l < r)
                    l++;
                swap(nums[l], nums[r]);
            }
            swap(nums[r], nums[mark]);
            quick_sort(nums, cl, l);
            quick_sort(nums, l + 1, cr);
        }
    }
};

堆排序

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

/**
 * 堆排序
*/
class Solution
{
  public:
    void sort(vector<int> &nums)
    {
        cout << " 堆排序 " << endl;
        int n=nums.size();
        for(int i = n/2-1; i>=0 ;i--)//  n是数组中数字的个数 
        {
            max_heapify(nums, i, n-1);
        }
        for(int i=n-1; i>0;i--){
            swap(nums[0],nums[i]);
            max_heapify(nums,0,i-1);
        }
    }

  private:
    void max_heapify(vector<int> &nums, int beg, int end)//beg和end是以数组下标计算
    {
        int parent=beg;
        int child=parent*2+1;
        while(child<=end){
            if(child+1<=end && nums[child+1] > nums[child])
                child++;
            if(nums[child] > nums[parent]){
                swap(nums[child],nums[parent]);
                parent=child;
                child=parent*2+1;
            }
            else break;
        }
    }
};

归并排序

• 算法原理
  归并排序具体工作原理如下（假设序列共有n个元素）：
  将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素
  将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
  重复步骤2，直到所有元素排序完毕
  归并排序是稳定的排序算法，其时间复杂度为O(nlogn)，如果是使用链表的实现的话，空间复杂度可以达到O(1)，但如果是使用数组来存储数据的话，在归并的过程中，需要临时空间来存储归并好的数据，所以空间复杂度为O(n)

/**
 * 归并排序
*/
class Solution{
public:
    void sort(vector<int> &nums)
    {
        cout << " 归并排序 " << endl;
        int size=nums.size();
        int i=1;
        while(i<size){
            int beg=0;
            int mid=beg+i-1<size-1?beg+i-1:size-1;
            int end=beg+2*i-1<size-1?beg+2*i-1:size-1;
            while(mid<end){
                merge_sort(nums,beg,mid,end);
                beg=end+1;
                mid=mid=beg+i-1<size-1?beg+i-1:size-1;
                end=beg+2*i-1<size-1?beg+2*i-1:size-1;
            }
            i*=2;
        }
    }
    private:
    void merge_sort(vector<int> &nums,int beg,int mid,int end){
        vector<int> temp;
        int pos1=beg;
        int pos2=mid+1;
        while(pos1<=mid || pos2<=end){
            if(pos1<=mid && pos2<=end){
                if(nums[pos1]<=nums[pos2]){
                    temp.push_back(nums[pos1]);
                    pos1++;
                }
                else{
                    temp.push_back(nums[pos2]);
                    pos2++;
                }
            }
            else if(pos1<=mid){
                temp.push_back(nums[pos1]);
                pos1++;
            }
            else{
                temp.push_back(nums[pos2]);
                pos2++;
            }
        }
        for(int i=0;i<=end-beg;i++){
            nums[beg+i]=temp[i];
        }
    }
};

int main()
{
    Solution sol;
    // vector<int> a {25, 34, -4, 0, 4, 9, 6, -1, 7, 2, 7, 25, 19, 20,-23,-11,43,29,1,0,0};
    vector<int> a {45, 34, 0, -4, 8,5,8};
    sol.sort(a);
    for (auto &w : a)
    {
        cout << w << " ";
    }
    cout << endl;
}