数据结构小结（九）排序算法大杂烩

心已赠人 2022-08-18 12:23 141阅读 0赞

## 冒泡排序 ##

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。

## 冒泡排序运作 ##

冒泡排序算法的运作如下：（从后往前） 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 3.针对所有的元素重复以上的步骤，除了最后一个。 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

## 排序代码 ##

void BubbleSort(RecordList L){
    
        int i,j,k;
        int t;
        for(i = 1;i <= L.length-1;j++){
            for(j = 1;j <= L.length -i ;j++){
                if(L.r[j] > L.r[j+1]){
                    t = L.r[j];
                    L.r[j] = L.r[j+1];
                    L.r[j+1] = t;
                }
            }
        }
    }
    
    一个递归实现
    
    void sort(int *add,int len)
    {
        int fact = 0 , isorderd = 0;
        if(len <= 1 || !add){
            return;
        }
    
        while(fact < len-1){
            if(add[fact] > add[fact+1]){
                add[fact]   ^= add[fact+1];
                add[fact+1] ^= add[fact];
                add[fact]   ^= add[fact+1];
                isorderd    = 1;
            }
            fact++;
        }
        if(!isorderd){
            return;
        }
        sort(add,len-1);
    }

## 插入排序 ##

时间复杂度：最坏的情况下为O(n^2)。
    
      适用场景： 对于小规模的输入来说，插入排序法是一个快速的排序算法，所以在规模很小的情况下
      ， 使用这种算法还是很有优势的。
    
      空间复杂度：它只需要一个元素的辅助空间，就是监视哨，用于元素交换所以空间复杂度为O（1）。
    
      稳定性：  插入排序是稳定的。
    
      适用性：  可以适用数组与链表两种存储方式

## 图解 ##

[![insert][]][insert 1]

## 简单实现 ##

#define MAXSIZE 1000
    
    typedef struct list{
    
        int r[MAXSIZE+1];
        int length;
    
    }list_array;
    
    
    void InsertSort(list_array L){
        int i,j;
        for(i = 2;i <= L.length;i++){
            if(L.r[i]< L.r[i-1]){
                L.r[0] = L.r[i];
                for(j = i-1;L.r[0]<L.r[j];j--)
                    L.r[j+1] = L.r[j];
                L.r[j+1] = L.r[0];
            }
        }
    }
    
    
    一个递归实现
    void sort(int *add,int len)
    {
        int fact  = 0;
        int index = 0;
        int obj   = add[len-1];
    
        if(len <= 1 || !add || len > lstlen){
            return;
        }
    
        index = len-1;
        while(fact < len-1){
            if(add[fact] > add[index]){
                break;
            }
            fact++;
        }
        while(index > fact){
            add[index] = add[index-1];
            index--;
        }
        add[fact] = obj;
        sort(add,len+1);
    }

## 选择排序 ##

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

## 时间复杂度,及稳定度分析 ##

选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。

[![paixu][]][paixu 1]

选择排序是一个不稳定的排序算法。

void SelectSort(RecordList L){
    
        int i,j,k;
        for(i = 1;i <= L.length-1;i++){
            k = i;
            for(j = i+1;j <= L.lenghth-1;j++){
                if(L.r[i] < L.r[k])
                    k = j;
                if(k != i){
                    t = L.r[i];
                    L.r[i] = L.r[k];
                    L.r[k] = t;
                }
            }
        }
    
    
    }
    
    上边是书上的一个代码
    下边的这个是递归的一个
    void sort(int *add,int len)
    {
        int fact  = 1;
        int index = 0;
        if(len <= 1 || !add){
            return;
        }
    
        index = 0;
        while(fact < len){
            if(add[fact] < add[index]){
                index = fact;
            }
            fact++;
        }
        if(index == 0){
            goto _DIGUI ;
        }
        add[0]     ^= add[index];
        add[index] ^= add[0]    ;
        add[0]     ^= add[index];
    _DIGUI:
        sort(add+1,len-1);
    }

## 折半插入排序 ##

折半插入排序（binary insertion sort）是对插入排序算法的一种改进，
    由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的
    数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。

## 具体操作 ##

在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a\[low\]，末元素设置为a\[high\]，则轮比较时将待插入元素与a\[m\]，其中m=(low+high)/2相比较,如果比参考元素小，则选择a\[low\]到a\[m-1\]为新的插入区域(即high=m-1)，否则选择a\[m+1\]到a\[high\]为新的插入区域（即low=m+1），如此直至low<=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a\[high+1\]。

## 稳定性与复杂度 ##

折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。附加空间O(1)。

折半查找只是减少了比较次数，但是元素的移动次数不变，所以时间复杂度为O(n^2)是正确的！

void BiInsertSort(Recordlist L){
        int i,j,k;
        int low,high;
    
        for(i = 2;i <= L.lenghth;i++){
            if(L.r[i] < L.r[i-1]){
                L.r[0] = L.r[i];
                low = 1;
                high = i-1;
                while(low <= high){
                    mid = (low + high)/2;
                    if(L.r[0] < L.r[mid]){
                        high = mid -1;
                    }else{
                        low = mid + 1;
                    }
    
                }
    
                for(j = i-1;j >= low;j--){
                    L.r[j+1] = L.r[j];
                    L.r[low] = L.r[0];
                }
            }
        }
    
    
    }

## 归并排序 ##

时间复杂度： O(nlog2N)

空间复杂度： 只需要一个空间O（N）

稳定性：稳定排序

[![merage][]][merage 1]

void merge(int *add,int len)
    {
        int lenA  = 0   , lenB = 0,lenC = 0,lentmp = 0;
        int *arrC = NULL;
    
        if(len <= 1){
            return;
        }
        arrC = (int *)malloc(len*sizeof(int));
        lentmp = len/2;
    
        merge(add,lentmp);
        merge(&add[lentmp],len-lentmp);
    
        lenA   = 0, lenB = lentmp;
        lenC   = 0;
    
        while((lenA != lentmp) && (lenB != len)){
             if(add[lenA] < add[lenB]){
                  arrC[lenC] = add[lenA];
                  lenA++;
             }else{
                  arrC[lenC] = add[lenB];
                  lenB++;
             }
             lenC++;
        }
    
        if(lenA == lentmp){
             while(lenB < len){
                 arrC[lenC++] = add[lenB++];
             }
        }else if(lenB == len){
             while(lenA < lentmp){
                 arrC[lenC++] = add[lenA++];
             }
        }else{
             //printf("all ok!\n");
        }
    
        memcpy(add,arrC,len*sizeof(int));
    
        free(arrC);
    }

## 快速排序 ##

快速排序（Quicksort）是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

设要排序的数组是A\[0\]……A\[N-1\]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是：

（1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；

（2）以第一个数组元素作为关键数据，赋值给key，即key=A\[0\]；

（3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A\[j\]，将A\[j\]和A\[i\]互换；

（4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A\[i\]，将A\[i\]和A\[j\]互换；

（5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A\[j\]不小于key,4中A\[i\]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

[![quick][]][quick 1]

### 代码实现 ###

int __quicksort(RecordList L,int low,int high){
    
        L.r[0] = L.r[low];
        while(low < high){
    
            while(low < high && L.r[high] >= L.r[0])
                --high;
            L.r[low] = L.r[high];
            while(low < high && L.r[low] < L.r[0])
                ++low;
            L.r[high] = L.r[low];
    
        }
        L.r[low] = L.r[0];
    
        return low;
    
    }
    
    
    void quicksort(RecordList L,int low,int high){
    
        if(low < high){
            pos = quicksort(L,low,high);
            __quicksort(L,low,pos-1);
            __quicksort(L,pos+1,high);
    
        }
    
    }

## 希尔排序 ##

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

一般的初次取序列的一半为增量，以后每次减半，直到增量为1。

这里上一个图 [![shell][]][shell 1]

时间复杂度：

O(N^(3/2)) ~ O(N^2)

空间复杂度依然同直接插入排序，只需要一个辅助空间。

稳定性：不稳定的排序算法

void shellSort(RecordList L,int dk){
        int i,j;
        for(i = dk=1;i <= L.length;i++){
            if(L.r[i] < L.r[i-dk]){
                L.r[0] = L.r[i];
                for(j = i-dk;j >0 && (L.r[0] < L.r[j]);j -= dk){
                    L.r[r+dk] = L.r[0];
                }
            }
        }
    }
    
    void shellSort_S(RecordList L,int dlta[]){
        int k;
        for(k = 0;k <L.length;k++)
            shellSort(L,dlta[k]);
    }
    
    
    一个递归实现
    void sort(int *add,int len,int gap)
    {
        int fst   = 0 , sec = 0    ;
        int index = 0 /*, gap = len/2*/;
    
        if(len <= 1 || !add){
            return;
        }
        if(0 == gap){
            return;
        }
    
        //while(gap != 0){
            for(fst=gap;fst<len;fst++){
                index = add[fst];
                for(sec=fst;sec>=gap;sec-=gap){
                    if(index < add[sec - gap]){
                        add[sec] = add[sec - gap];
                    }else{
                        break;
                    }
                }//end for[sec]
                add[sec] = index;
            }//end for[fst]
            //gap /= 2;
            //display(add,len);
        //}//end while[gap]
        sort(add,len,gap/2);
    }
    
     如果去掉注释就是非递归的

[insert]: /images/20220731/a9b52d607e7e4af69ada43f2f44ec386.png
[insert 1]: https://github.com/zmr961006/DSAA/blob/master/chap9_sort/insert.jpg
[paixu]: /images/20220731/d56403178a854de38e30d361cc4733f0.png
[paixu 1]: https://github.com/zmr961006/DSAA/blob/master/chap9_sort/paixu.jpg
[merage]: /images/20220731/411193b6f8ab4dc0a197fa2f43a03aff.png
[merage 1]: https://github.com/zmr961006/DSAA/blob/master/chap9_sort/merage.jpg
[quick]: /images/20220731/06c3e4a06043472ebc27efb18b82acc9.png
[quick 1]: https://github.com/zmr961006/DSAA/blob/master/chap9_sort/quicksort.jpg
[shell]: /images/20220731/609c63efce484a59812a48ba3752689b.png
[shell 1]: https://github.com/zmr961006/DSAA/blob/master/chap9_sort/shell.jpg