数据结构之排序

作者: 赤霄_chaos | 来源:发表于2020-04-06 14:45 被阅读0次

排序作为计算机程序设计中的一种重要运算，在实际中应用很广，据-统计，计算机处理的25%的机时是用于排序的。

1、排序的分类

根据排序中所涉及的存储器，可将排序分为内部排序和外部排序两大类
1、内部排序：排序过程中，所有记录都放在内存中处理的是内部排序。
2、外部排序：当待排序的记录太多，排序是不仅要使用内存，而且还要使用外部存储器的排序方法是外部排序。

2、排序算法的性能分析

稳定性
1、稳定：如果待排序的记录中，存在多个关键字相同的记录，经排序后这些记录的相对次序仍然保持不变。
2、不稳定：如果待排序的值中，存在多个关键字相同的值，经排序后这些值的相对次序发生改变，称为不稳定的排序。
时间复杂度
1、时间复杂度可以认为是对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
2、常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)。
3、时间复杂度O(1)：算法中语句执行次数为一个常数，则时间复杂度为O(1)。
空间复杂度
1、算法在计算机内执行时所需存储空间的度量，它也是问题规模n的函数。
2、空间复杂度O(1)：当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)。
3、空间复杂度O(log2N)：当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n) ax=N，则x=logaN。
4、空间复杂度O(n)：当一个算法的空间复杂度与n成线性比例关系时，可表示为0(n)。
复杂度分析： 1.png

3、排序算法

3.1、冒泡排序（Bubble Sort）

基本思路：从R1开始，两两比较相邻值的关键字，即比较Ri和Ri+1（i=1，2，...，n-1）的关键字大小，若逆序（如Ki > Ki+1）,则交换Ri 和Ri+1的位置，如此经过一趟排序，关键字最大的记录被安置在最后一个位置（Rn）上。然后再对前n-1个记录进行同样的操作，具有次大关键字的值被安置在Rn-1上。如此反复。

void BobbleSort(int array[],int N){
    bool bExchangeFlag;
    for (int i = 1; i < N; i++) { //最多做length-1趟排序
          bExchangeFlag = false; //
        for (int j = 0; j < N - i; j++) {
            if (array[j] > array[j+1]) {
                swap(&array[i], &array[j+1]);
                bExchangeFlag = true;
            }
        }
        if (!bExchangeFlag) {//本趟排序未发生交换，则提前终止算法
            break;
        }
    }
}

3.1.1、性能分析

稳定性：不稳定
分类：内排序
时间复杂度
(1)最好情况：O(n)--正好是正序的，不需要交换数据
(2)最坏情况：O $(n^{2})$ --逆序
(3)平均复杂度：O(n)
(4)空间复杂度：O(1)

3.2、插入排序（Insertion Sort）

基本思路：构建有序序列，对于未排序数据，在已排序中从后向前扫描，找到相应位置插入，直到将未排序队列过滤完毕。
排序过程如下：

2.png

void Insertion_Sort(int array[],int N){
    for (int p = 1; p < N; p++) {
        int temp = array[p];
        int I;
        for (i = p; p > 0 && array[i-1] > temp; i--) {
            array[i] = array[i-1];
        }
        array[i] = temp;
    }
}

3.2.1、性能分析

稳定性：稳定
分类：内排序
时间复杂度
(1)最好情况：O(n)--当待排序数组是有序时
(2)最坏情况：O $(n^{2})$ )--待排序数组是逆序时
(3)平均复杂度：O(n)
(4)空间复杂度：O(1)

3.3、希尔排序（Shell Insertion Sort）

基本思路：定义增量序列 $D _{M}$ > $D _{M-1}$ >...> $D _{1}$ = 1,对每个 $D _{k}$ 进行“ $D _{k}$ 间隔”插入排序 $_{(k=M,M-1,...1)}$ 。
注意：“ $D _{k}$ 间隔”有序的序列，在执行“ $D _{k-1}$ 间隔”排序后，仍然是“ $D _{k}$ 间隔”有序的。
排序过程如下：

3.png

#include<stdio.h>
#include <math.h>
#define MAXNUM 10
//根据当前增量进行插入排序
void shellInsert(int array[],int n,int dk)
{
    int i,j,temp;
    for(i=dk;i<n;i++)//分别向每组的有序区域插入
    {
        temp=array[I];
        for(j=i-dk;(j>=i%dk)&&array[j]>temp;j-=dk)//比较与记录后移同时进行
            array[j+dk]=array[j];
        if(j!=i-dk)
            array[j+dk]=temp;//插入
    }
}

//计算Hibbard增量
int dkHibbard(int t,int k)
{
    return (int)(pow(2,t-k+1)-1);
}
 
void Shell_Sort(int array[],int n,int t)
{
    for(int i=1;i<=t;i++)
       shellInsert(array,n,dkHibbard(t,i));
}

void ShellSort(void){
    int array[] = {1,10,3,5,4,2,15,9,54,18};
    Shell_Sort(array,MAXNUM,(int)(log(MAXNUM+1)/log(2)));//排序趟数应为log2(n+1)的整数部分
       for(int i = 0;i< MAXNUM;i++)
           printf("%d ",array[I]);
}

再看一个序列：1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 16

4.png

可以看到增量元素不互质，则小增量可能不起作用，所以选择增量序列模式很重要。
目前主流增量序列：
Hibbard 增量序列： $D_{k}$ = $2^{k}$ - 1 相邻元素互质
最坏情况：T = O $(N^{5/4})$
猜想： $T_{avg}$ = O $(N^{3/2})$
Sedgewick 增量序列：{1,5,19,41,109,...}
9 $\times4^{i}$ -9 $\times 2^{i}$ +1或 $4^{i}$ -3 $\times2^{i}$ +1
猜想： $T _{avg}$ = O $(N^{7/6})$ ， $T _{worst}$ = O $(N^{4/3})$

3.3.1、性能分析

稳定性：不稳定
分类：内排序
时间复杂度
(1)最好情况：O( $n$ )
(2)最坏情况：O( $n^{2}$ )
(3)平均复杂度：O( $n$ )
(4)空间复杂度：O( $1$ )

3.4、快速排序（Shell Insertion Sort）

基本思路：设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的最后一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，将该数组分成2个数组，再递归的处理左边数组和右边数组。
排序过程如下：

5.png

int Median(int array[],int left,int right){
        int center = (left + right)/2;
        if (array[left] > array[center]) {
            swap(&array[left], &array[center]);
        }
        if (array[left] > array[right]) {
            swap(&array[left], &array[right]);
        }
        if (array[center] > array[right]) {
            swap(&array[center], &array[right]);
        }
        swap(&array[center], &array[right - 1]);
        return array[right - 1];
}

void QickSort(int array[],int left,int right){
    
    if (1 < right-left) {
         int pivot = Median(array, left, right);
         int i = left;
         int j = right - 1;
         for (;;) {
             while (array[++i] < pivot) {}
             while (array[--j] > pivot) {}
             if (i < j) {
                 swap(&array[i], &array[j]);
             }else{
                 break;
             };
         }
         swap(&array[i], &array[right - 1]);
         QickSort(array, left, i-1);
         QickSort(array, i+1, right);
    }
}

void quick_sort(int array[],int N){
     QickSort(array, 0, N - 1);
}

void quicksort(void){
   int tree[] = {1,10,3,5,4,2,15,9,54,18};
   int n = 10;
   quick_sort(tree, 10);
   for (int i = 0; i < n; i++) {
       printf("%d ",tree[I]);
   }
}

3.4.1、性能分析

稳定性：不稳定
分类：内排序
时间复杂度
(1)最好情况：O(n $log_{2}n$ )--当待排序数组是有序时
(2)最坏情况：O $(n^{2})$ --待排序数组是逆序时
(3)平均复杂度：O(n $log_{2}n$ )
(4)空间复杂度：O(n $log_{2}n$ )

3.5、直接选择排序（Selection Sort）

基本思路：从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，把它与第一元素交换存储位置，然后再在余下的元素中选出此小的，把它与第二元素交换，以此类推，直到排序完成。
排序过程如下：

5.png

void Select_Sort(int array[],int N){
    int nMinIndex;//用于记录最小元素的下标值
    for(int i = 0;i < N - 1;i++){
        nMinIndex = I;
        for (int j = i + 1; j < N; j++) {
            if (array[j] < array[nMinIndex]) {
                nMinIndex = j;
            }
        }
        if (nMinIndex != i) {
            swap(&array[nMinIndex], &array[I]);
        }
    }
}

3.5.1、性能分析

稳定性：不稳定
分类：内排序
时间复杂度
(1)最好情况：O $(n^{1.3})$ --当待排序数组是有序时
(2)最坏情况：O $(n^{2})$ --待排序数组是逆序时
(3)平均复杂度：O(n)
(4)空间复杂度：O(1)

3.6、归并排序（Merge Sort）

基本思想：指的是将两个顺序序列合并成一个顺序序列的排序方法。
归并排序的实现方法：
3.6.1递归方法

6.png

//L = 左边起始位置，R= 右边起始位置，RightEnd 右边终点位置
void Merge(int Array[],int TempArray[],int L,int R,int RightEnd){
    int LeftEnd = R - 1;
    int Temp = L; //存放结果数组的起始位置
    int NumCount = RightEnd - L + 1;
    while (L<=LeftEnd && R <= RightEnd) {
        if (Array[L] <= Array[R]) {
            TempArray[Temp++] = Array[L++];
        }else{
            TempArray[Temp++] = Array[R++];
        }
    }
    
    while(L <= LeftEnd) { //直接复制左边剩下的元素
         TempArray[Temp++] = Array[L++];
    }
    while(R <= RightEnd) {//直接复制右边剩下的元素
         TempArray[Temp++] = Array[R++];
    }
    
    for(int i = 0;i < NumCount;i++,RightEnd--){
        Array[RightEnd] = TempArray[RightEnd];
    }
}

void MSort(int Array[],int TempArray[],int L,int RightEnd){
    int Center;
    if (L < RightEnd) {
        Center = (L + RightEnd)/2;
        MSort(Array, TempArray, L, Center);
        MSort(Array, TempArray, Center+1, RightEnd);
        Merge(Array, TempArray, L, Center+1, RightEnd);
    }
}

void Merge_Sort(int Array[],int N){
    int *tempArray = (int *)malloc(N*sizeof(int));
    if (tempArray != NULL) {
        MSort(Array, tempArray, 0, N-1);
    }
}

3.6.2非递归方法

7.png

void MergePass(int Array[],int TempArray[],int L,int R,int RightEnd){
    int LeftEnd = R - 1;
    int Temp = L; //存放结果数组的起始位置
    int NumCount = RightEnd - L + 1;
    while (L<=LeftEnd && R <= RightEnd) {
        if (Array[L] <= Array[R]) {
            TempArray[Temp++] = Array[L++];
        }else{
            TempArray[Temp++] = Array[R++];
        }
    }
    
    while(L <= LeftEnd) { //直接复制左边剩下的元素
         TempArray[Temp++] = Array[L++];
    }
    while(R <= RightEnd) {//直接复制右边剩下的元素
         TempArray[Temp++] = Array[R++];
    }
}

void Merge_pass(int array[],int TempArray[],int N,int length){ //有序序列长度
    for (int i = 0; i < N - 2*length; i +=2*length) {
        Merge(array, TempArray, i, i+length, i + 2*length - 1);
        if (i + length < N) {
            MergePass(array, TempArray, i, i + length, N-1);
        }else{
            for (int j = i; j < N; j++) {
                TempArray[j] = array[j];
            }
        }
    }
}


void Merge_no_recursion_Sort(int Array[],int N){
    int length = 1;//子序列长度
    int *tempArray = (int *)malloc(N*sizeof(int));
    if (tempArray != NULL) {
        while (length < N) {
            Merge_pass(Array, tempArray, N, length);
            length *= 2;
            Merge_pass(tempArray, Array, N, length);
            length *= 2;
        }
        free(tempArray);
    }
}

3.6.3、性能分析

性能分析：
稳定性：稳定
分类：内排序
时间复杂度
(1)最好情况：O( $nlog _{}$ n)
(2)最坏情况：O( $nlog _{}$ n)
(3)平均复杂度：O( $nlog _{}$ n)
(4)空间复杂度：O(n)

3.7、计数排序（Count Sort）

计数排序是一种非比较排序算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序。

基本思想：计数排序的基本思想就是对每一个输入元素x，确定小于x的元素个数，我们就可以直接把x放到最终输出数组中的相应位置上。
排序过程：
1、查询待数组中的最大值和最小值，根据最大元素和最小元素的差值（max-min+1）,申请额外空间。
2、遍历待排序数组，将每一个元素出现次数（value）记录到元素值（key）对应的额外空间内。
3、从额外空间的第二个元素开始，将当前元素个数加上前一个元素的个数，即可确定序列中值小于x的元素的个数，也就确定了元素x的位置。
4、将待排序数组的元素倒序移动到新数组中。

示例：

8.png

#include<stdlib.h>
#include<string.h>
#define MAXNUM 10
void Count_Sort(int Array[],int N){
    int Max = Array[0];
    int Min = Array[0];
    for (int i = 1; i < N-1; i++) {
        if (Array[i] >= Max) {
            Max = Array[i];
        }else if(Array[i] <= Min){
            Min = Array[i];
        }
    }
    int size = Max - Min +1;
    int* Array_B = (int*)malloc(size*sizeof(int));
    memset(Array_B, 0, sizeof(int)*size);
    for (int i = 0; i < N; i++) {
        Array_B[Array[i] - Min]++;
    }
    
    for (int i = 1; i < size; i++) {
        Array_B[i] = Array_B[i] + Array_B[i - 1];
    }
      
    int* Array_C= (int *)malloc((N)*sizeof(int));
    memset(Array_C, 0, sizeof(int)*size);
    for (int i = N-1; i >= 0; i--) {
         Array_B[Array[i] - Min]--;
         Array_C[Array_B[Array[i] - Min]] = Array[i];
     }
    for (int i = 0; i < N; i++) {
        Array[i] = Array_C[i];
    }
    free(Array_B);
    free(Array_C);
    Array_B = NULL;
    Array_C = NULL;
}

void CountSort(void){
    int array[] = {1,10,3,5,4,2,15,9,54,18};
    Count_Sort(array,MAXNUM);//排序趟数应为log2(n+1)的整数部分
       for(int i = 0;i< MAXNUM;i++)
           printf("%d ",array[i]);
}

3.8、基数排序（Radix Sort）

基本思想：将整数按位数切割成不同的数字，然后按每个位数分别比较。
排序过程：
1、所有待排序整数统一成位数相同的数值，位数不够的整数需要将缺位补零。
2、从低位开始比较，依此进行排序。
3、从低位到高位比较完成后，待排序数组就是一个有序数组。


//获取数字位数
#include <math.h>
#define MAXNUM 10
int getLoopTimes(int num){
    int count = 1;
    int temp = num/10;
    while (temp != 0) {
        count++;
        temp = temp/10;
    }
    return count;
}
//查询数组中的最大值
int findMaxNum(int *p,int n){
    int max = 0;
    for (int i = 0;i < n;i++) {
        if (*(p + i) > max) {
            max = *(p+i);
        }
    }
    return max;
}

void Radix_Sort(int *p,int n,int loop){
    int buckets[10][MAXNUM] = {};//建立一组桶此处的MAXNUM是预设的根据实际数情况修改，
    int tempNum = (int)pow(10,loop - 1);//求整数各占位的数字
    for (int i= 0; i < n; i++) {
        int row_index = (*(p + i)/tempNum)%10;
        for (int j = 0;j < MAXNUM;j++) {
            if(buckets[row_index][j] == 0) {
                buckets[row_index][j] = *(p + i);
                break;
            }
        }
    }
    int k = 0;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < MAXNUM; j++) {
            if (buckets[i][j] != 0) {
                *(p + k) = buckets[i][j];
                buckets[i][j] = 0;
                k++;
            }
        }
    }
}

void bucketSort(int *p,int n){
    int maxNum = findMaxNum(p, n);//获取数组中的最大数
    int loopTimes = getLoopTimes(maxNum);//获取最大数的位数
    for (int i = 1;i <= loopTimes;i++) {
        Radix_Sort(p, n, i);
    }
}

void RadixSort(){
     int array[] = {512,240,666,520,43,76};
     int *array_p = array;
     int size = sizeof(array)/sizeof(int);
     bucketSort(array_p, size);
     for(int i = 0; i < size; i++){
        printf("%d\n", array[i]);
     }
}

3.8、桶排序（Bucket Sort）

基本思想：根据元素值特性将待排序集合拆分成多个区域，将这些区域称为桶，这些值域（桶）是处于有序的状态。对桶中元素进行排序后，所以元素就处于有序状态了。
思想交换：
1、快速排序是将待排序集合拆分成两个值域（桶）（一个有序队列，一个无序队列，也可以说是两个桶），分别对两个值域（桶）进行排序，有一点不同的是快排是原地排序，是对集合本身排序，而桶排序是多个值域（桶），对每个值域（桶）排序，桶排序需要额外的空间，在额外空间对桶进行排序，避免构建桶的过程的元素交换和比较，同时可以自主选择恰当的排序算法。
2、对计数排序的改进，计数排序也需要额外操作空间，额外空间跨度从最小值到最大值，如果待排序序列不是依次递增的，就会造成操作空间的浪费。桶排序则弱化操作空间的浪费，将从最小值到最大值每个值都申请空间，改进成从最小值到最大值按照一定数值特性分成固定区域申请空间，尽量减少由于元素值不连续而造成的空间浪费。
桶排序过程中两个关键环节【1】：
1、元素值域的划分，也就是元素到桶的映射规则。映射规则需要根据待排序集合的元素分布特性进行选择，若规则设计的过于模糊、宽泛，则可能导致待排序集合中所有元素全部映射到一个桶上，则桶排序向比较性质排序算法演变。若映射规则设计的过于具体、严苛，则可能导致待排序集合中每一个元素值映射到一个桶上，则桶排序向计数排序方式演化。
2、排序算法的选择，从待排序集合中元素映射到各个桶上的过程，并不存在元素的比较和交换操作，在对各个桶中元素进行排序时，可以自主选择合适的排序算法，桶排序算法的复杂度和稳定性，都根据选择的排序算法不同而不同。
示例：
待排序集合为：[-7, 51, 3, 121, -3, 32, 21, 43, 4, 25, 56, 77, 16, 22, 87, 56, -10, 68, 99, 70];
映射规则为:

待续。。