排序 - 十大排序算法

浙大 MOOC 数据结构

复杂度分析

排序算法 平均时间复杂度 最差时间复杂度 空间复杂度 数据对象稳定性
冒泡排序 O(N^2) O(N^2) O(1) 稳定
选择排序 O(N^2) O(N^2) O(1) 数组不稳定、链表稳定
插入排序 O(N^2) O(N^2) O(1) 稳定
快速排序 O(NlogN) O(N^2) O(logN) 不稳定
堆排序 O(NlogN) O(NlogN) O(1) 不稳定
归并排序 O(NlogN) O(NlogN) O(N) 稳定
希尔排序 O(N^d) O(N^2)) O(1) 不稳定
计数排序 O(N+m) O(N+m) O(N+m) 稳定
桶排序 O(N) O(N) O(m) 稳定
基数排序 O(k*n) O(N^2 ) 稳定
  • 均按从小到大排列
  • k：代表数值中的 “数位” 个数
  • n：代表数据规模
  • m：代表数据的最大值减最小值
  • 来自：wikipedia . 排序算法

排序算法的比较

  • 简单选择排序, 冒泡排序, 直接插入排序, 算法都很好写,排序也不需要额外的空间; 但是时间复杂度都比较差;

  • 简单选择排序是跳着交换的,导致这个算法可能不稳定;

  • 希尔排序算法好坏很大程度依赖于增量序列的选择; 最坏 d = 2;

  • 堆排序和归并排序理论上讲时间复杂度是最好的; 无论如何都是O(NlogN)

  • 归并排序的缺点是额外需要一个O(N)的空间 ; 当数据量非常大, 可能只能排序一半,因为空间问题 ;

  • 堆排序的时间复杂度虽然是O(NlogN), 但是O这个常数比较大, 所以他和快排速度速度相比还是有待商议;

  • 堆排序, 快排都不稳定; 快排总可以构造一个最坏情况使得它的时间复杂度是O(N^2) 这个数量级 ; 因为快排是递归的, 所以总会需要额外的空间 O(logN); 在实际应用中快排的时间复杂度常数比较小, 所以很快;

  • 基数排序在某种情况在会比O(NlogN) 还快, 快到近乎线性; 但是这就取决于需要多好个桶 Bucket , 需要多好次的分配和收集; 所以它的额外时间复杂度就是O(P(N+B)) ; 额外空间复杂度也是需要 B 个桶, 留出 N 个空间, 给他放进去; 空间复杂度就是O(N+B) ; 所以什么情况下划算, 也需要看情况; 好处就是实现正确的话, 基数排序也是稳定的;

9.1 冒泡排序

冒泡排序

最好情况 T= O(n)
最坏情况T= O(n^2)

void bubbleSort(int a[], int length){
    for(int i=length-1;i>=0;i--){
        int flag = 0;
        for(int j=0;j<i;j++){
            if(a[j]>a[j+1]){
                swap(a[j],a[j+1]);
                flag = 1;
            }
        }
        if(flag == 0){
            break;//无交换 说明有序, 退出循环;
        }
    }
}

9.2插入排序

插入排序.gif

基本思想：

从第2张牌开始排序
取出未排序序列中的第一个元素
插到前面已经排好的序列中，比较并右移，使得插入后序列也是排好顺序的
按照此法对所有元素进行插入，直到整个序列排为有序的过程

时间复杂度：

最好情况，顺序T= O(n)
最坏情况，逆序T= O(n^2)
稳定性：是

序列基本有序, 插入排序简单高效;

定理:

void insertSort(int a[] , int length){
    for(int i =1;i<length;i++){
        int tmp = a[i];
        int j = 0;
        for(j= i;j>0 && tmp<a[j-1];j--){
            a[j] = a[j-1];
        }
        a[j] = tmp;
    }
}

时间复杂度下界

i \lt j \ \ \ 且 A[i] \gt A[j] 则称(i,j)是一对逆序对;

I : 为原始逆序列里面的个数

问题：序列{34, 8, 64, 51, 32, 21}中有多少逆序对?
——(34,8) (34,32) (34,21) (64,51) (64,32) (64,21) (51,32) (51,21) (32,21)

交换2个相邻元素正好消去一个逆序对！

插入排序: T(N,I) = O(N+I)

N为序列长度，I为逆序对个数

——如果序列基本有序，则插入排序简单且高效---

定理：任意N个不同元素组成的序列平均具有\frac{N(N-1)}{4}个逆序对

定理：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为Ω(𝑁^2)

这意味着：要提高算法效率，我们必须

\Rightarrow每次消去不止一个逆序对

\Rightarrow每次交换相隔较远的2个元素

9.3 希尔排序

希尔排序.gif

初始序列为{81,94,11,96,12,35,17,95,28,58,41,75,15}

首先按照5间隔取子序列排序，即首先取{81,35,41}进行排序，然后依次取{94,17,75}，{11,95,15}，{96,28}，{12,58}进行子序列排序，之后再将子序列合并成总的序列即{35,17,11,28,12,41,75,15,96,58,81,94,95}

同理对5间隔排序后得到的序列进行3间隔排序可以得到序列{28,12,11,35,15,41,58,17,94,75,81,96,95}

最后对3间隔的序列做1间隔排序

归纳为：

定义增量序列𝐷𝑀>𝐷𝑀−1>...>𝐷1=1

对每个𝐷_𝑘进行D_k间隔排序（k=M,M-1,...,1）

注意：𝐷_𝑘间隔有序序列，在执行𝐷_𝑘−1间隔排序后，仍然是𝐷𝑘间隔有序的原始希尔增量序列 ;

原始希尔排序 ： 𝐷_𝑀=⌊\frac {𝑁}{2}⌋,𝐷_𝑘=⌊\frac {𝐷_𝑘}{2}⌋

void shellSort(int A[], int N){
    for(int D = N/2; D>0; D = D/2){
        for(int i =D;i<N;i+=D){
                int tmp = A[i];
                int j ;
                for(j=i;j>=D && tmp<A[j-D];j-=D){
                    A[j] = A[j-D];
                }
                A[j] = tmp;
            }
        }    
}

最坏情况:
T = \Theta (N^2)

增量元素不互质, 小增量可能根本不会起作用;

解决办法是使用更好的增量序列;

  • Hibbard增量序列

𝐷_𝑘=2^𝑘−1——相邻元素互质
最坏情况：𝑇=Θ(𝑁^ \frac{3} { 2})
猜想：𝑇_{𝑎𝑣𝑔}=𝑂(𝑁^ \frac {5} { 4} )

  • Sedgewick增量序列

{{1，5，19, 41, 109，...}}

9*4^i - 9* 2^i + 1\ 或 \ 4^i - 3* 2^i + 1

猜想：𝑇_{𝑎𝑣𝑔}=𝑂(𝑁^\frac{7}{6}),𝑇_{𝑤𝑜𝑟𝑠𝑡}=𝑂(𝑁^\frac{4}{3})

9.4 选择排序

选择排序.gif

选择排序
思路：

先从A[i]到A[N–1]中直接扫描找最小元，记录其位置
将A[i]与处于最小元位置的元素进行交换
堆排序
思路：与选择排序类似，但是改变最小元的扫描策略，利用堆结构扫描

void Selection_Sort( ElementType A[], int N )
{
    int i, MinPosition;
    for ( i=0; i<N; i++ )
    {
        // 从A[i]到A[N–1]中找最小元，并将其位置赋给MinPosition
        MinPosition = ScanForMin( A, i, N-1 );
        // 将未排序部分的最小元换到有序部分的最后位置
        Swap( A[i], A[MinPosition])
    }
}

实现版本一:

int ScanForMin(int A[], int index, int N){
    int MinTmp = A[index];
    int position = index;
    for(int i = index; i<N;i++){
        if(A[i]<MinTmp){
            position = i;
            MinTmp = A[i];
        }
    }
    return position;
}

void selectionSort(int A[], int N){
    for(int i = 0; i< N;i++){
        int MinPosition = ScanForMin(A, i, N);
        swap(&A[i],&A[MinPosition]);
    }
   
}

实现版本二:

void select_sort(int a[], int n){
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(a[j]<a[i]){
                swap(a[j],a[i]);
            }
        }
    }
}

9.5 堆排序

堆排序.gif

算法1

思路：

  • 首先将数组调整为最小堆
  • 利用一个临时数组存储依次弹出的根结点
  • 将临时数组直接赋值给原数组

因此：

  • 算法1的最终时间复杂度为T(N) = O(NlogN);

  • 但是需要额外的O(N)空间，并且复制元素需要时间

void Heap_Sort( ElementType A[], int N )
{
    BuildHeap(A); // 将数组A调整为堆，复杂度为O(N)
    for ( i=0; i<N; i++ )
        TmpA[i] = DeleteMin(A);  // 依次弹出根结点，此时 O(logN)
    for ( i=0; i<N; i++ ) 
        A[i] = TmpA[i]; // 直接赋值，此时复杂度为O(N)
}

算法2：

思路：

  • 先将数组调整为一个最大堆

  • 将根结点与堆的最后一个元素进行交换

  • 删除堆的倒数第一个元素，存至数组的末尾，重新对堆进行最大堆的调整;

  • 直到堆的元素为1

/* 交换 */
void Swap( ElementType *a, ElementType *b )
{
    ElementType t = *a; *a = *b; *b = t;
}

/* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */ 
void PercDown( ElementType A[], int p, int N )
{
    int Parent, Child;
    ElementType X;
 
    X = A[p]; /* 取出根结点存放的值 */
    for( Parent=p; (Parent*2+1)<N; Parent=Child ) 
    {
        Child = Parent * 2 + 1;
        if( (Child!=N-1) && (A[Child]<A[Child+1]) )
            Child++;  /* Child指向左右子结点的较大者 */
        if( X >= A[Child] ) 
            break; /* 找到了合适位置 */
        else  /* 下滤X */
            A[Parent] = A[Child];
    }
    A[Parent] = X;
}

/* 堆排序 */
void HeapSort( ElementType A[], int N ) 
{ 
    int i;
       
    for ( i=N/2-1; i>=0; i-- )/* 建立最大堆 */
        PercDown( A, i, N );
      
    for ( i=N-1; i>0; i-- ) 
    {
        /* 删除最大堆顶 */
        Swap( &A[0], &A[i] );
        PercDown( A, 0, i );
    }
}

9.6归并排序

归并排序.gif

核心思想：有序子列的归并


如果两个子序列一共有 N 个元素, 则归并的时间复杂度是:

T(N) = O(N)

将子序列A,B的元素依次比较，合并成C序列;

递归算法

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

可以推得：

\ \ \ \ \ \ \ \ \ \ \ \ \ \ T(N) = T(N/2)+T(N/2)+O(N)

\ \ \ \ \ \ \ \ \ \ \ \ \Rightarrow \ \ \ \ \ \ \ \ \ \ T(N)=O(N logN )

算法实现:

void Merge(int A[], int TmpA[], int L, int R, int RightEnd){
    int beginIndex = L ;
    int LeftEnd = R -1;
    int i = L;
    while(L<= LeftEnd && R<= RightEnd){
        if(A[L]<=A[R]){
            TmpA[i++] = A[L++];
        }else{
            TmpA[i++] = A[R++];
        }
    }
    while(L <= LeftEnd){
        TmpA[i++] = A[L++];
    }
    while(R <= RightEnd){
        TmpA[i++] = A[R++];
    }
    //TmpA 元素 赋值 给 A
    for(int j = RightEnd;j>=beginIndex;j--){
        A[j] = TmpA[j];
    }

}
void mergeSort(int A[],int TmpA[], int L,int R){
    // int * TmpA = (int *)malloc(sizeof(int)*N) ;
    int Center ;
    if(L<R){
        Center = (L+R)/2+1;
        mergeSort(A,TmpA,L,Center-1);
        mergeSort(A, TmpA,Center,R);
        Merge(A,TmpA,L,Center,R);
    }
}
void mergeSort(int A[], int N){
    int * TmpA = (int * )malloc(sizeof(int)*N);
    if(TmpA != NULL){
        mergeSort(A,TmpA,0,N-1); 
        free(TmpA);    
    }else{
        printf("\n 空间不足 \n");
    }
}

非递归算法:


思路：

  • 首先对长度为N的序列相邻的两个元素进行排列，

  • 然后合并成N/2个子序列，对相邻的子序列进行合并排序

  • 依次类推，直至合并成为长度为N的序列

由图可知，需要额外的O(N)内存空间进行临时值得存储

算法实现:

void Merge1(int A[],int TmpA[],int L,int R,int RightEnd){
    int LeftEnd = R-1;
    int i = L;
    while(L<=LeftEnd && R<=RightEnd){
        if(A[L]<=A[R]){
            TmpA[i++] = A[L++];
        }else{
            TmpA[i++] = A[R++];
        }
    }
    while(L<=LeftEnd){
        TmpA[i++] = A[L++];
    }
    while(R<=RightEnd){
        TmpA[i++] = A[R++];
    }
}
void Merge_Pass(int A[],int TmpA[], int N, int length){
    int i=0;
    for( i=0;i<=N-2*length;i+=2*length){
        Merge1(A,TmpA,i,i+length,i+2*length-1);
    }
    if(i+length<N){
        Merge1(A,TmpA,i,i+length,N-1);
    }else{
        for(int j=i;j<N;j++){
            TmpA[j] = A[j];
        }
    }
}
void MergeSort2(int A[],int N){
    int * TmpA = (int *)malloc(sizeof(int)*N);
    if(TmpA!=NULL){
        int length = 1;
        while(length<N){
            Merge_Pass(A,TmpA,N,length);
            length*=2;
            Merge_Pass(TmpA,A,N,length);
            length*=2;
        }
        free(TmpA);
    }else{
        printf("\n 内存分配失败;\n");
        exit(0);
    }
}

10.1 快速排序

快速排序.gif

快速排序思路：

  1. 选取第一个数为基准
  2. 将比基准小的数交换到前面，比基准大的数交换到后面
  3. 对左右区间重复第二步，直到各区间只有一个数

方法: 分而治之

最好情况?

每次正好中分 => T(N) = O(NlogN)

最坏情况?

中分 pivot = A[0]

1 2 3 4 5 6 ... N-1 N
  2 3 4 5 6 ... N-2 N
    3 4 5 6 ... N-2 N

T(N) = N(N)+T(N-1)

\ \ \ \ \ \ \ \ \ = O(N) + O(N-1) + T(N-2)

\ \ \ \ \ \ \ \ \ = O(N) + O(N-1)\ +\ ...\ +\ O(1)

\ \ \ \ \ \ \ \ \ = O(N^2)

选主元(pivot; 取法对于运行速度还是有影响的)

  • 随机取: rand()函数时间也不便宜
  • 取头, 中, 尾巴中位数

CUT_OFF的设置是一个需要考量的因素

#define CUT_OFF 100 //定义一个阈值,因为数据元素不是很多时候,插排比快排好
//主元
ElementType Median3(ElementType A[],int Left, int Right){
    int Center = (Left + Right)/2 + 1;
    if(A[Left]>A[Center]){swap(&A[Left],&A[Center]);}
    if(A[Left]>A[Right]){swap(&A[Left],&A[Right]);}
    if(A[Right]>A[Center]){swap(&A[Right],&A[Center]);}

    swap(&A[Center],&A[Right-1]);
    return A[Right-1];
}
void Quick_Sort(ElementType A[], int Left, int Right){
    if(Right-Left>CUT_OFF){
        ElementType Pivot = Median3(A,Left, Right);
        int i = Left;
        int j = Right-1;
        for(;;){
            while(A[++i]<Pivot){}
            while(A[--j]>Pivot){}
            if(i<j){
                swap(&A[i],&A[j]);
            }else{
                // swap(&A[j],&A[Right-1]);
                break;
            }
        }
        swap(&A[i],&A[Right-1]);
        Quick_Sort(A,Left,i-1);
        Quick_Sort(A,i+1,Right);

    }else{
        selectionSort(A+Left,Right-Left+1);
    }
}
void quickSort(ElementType A[],int N){
    Quick_Sort(A,0,N-1);
}

10.2 计数排序

计数排序.gif

计数排序：统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引i位（i≥0）。

计数排序基于一个假设，待排序数列的所有数均为整数，且出现在（0，k）的区间之内。

如果 k（待排数组的最大值） 过大则会引起较大的空间复杂度，一般是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。

计数排序不是比较排序，排序的速度快于任何比较排序算法。

时间复杂度为 O（n+k），空间复杂度为O（n+k）

算法的步骤如下：

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
  3. 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）
  4. 反向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1
/**
 * @brief 计数排序算法
 * 
 * @param A 
 * @param B 
 */
void Count_Sort(vector<int> &A, vector<int> &B){
 
    if(A.size() == 0){
        return ;
    }
    int max = (*max_element(begin(A),end(A)));//最大元素
    vector<int> CountA(max+1,0);

    for(int i = 0;i<A.size();i++){
        CountA[A[i]]++;
    }
    int k = 0;
    for(int i= 0;i<max+1;i++){
        if(CountA[i]!=0){
            //  打印统计的个数
            //  printf("\n%d %d",i,CountA[i]);
            for(int j=0;j<CountA[i];j++){
                B[k++] = i;
            }
        }
    }
}
void countSort(ElementType A[], int N){
    vector<ElementType>TmpA(A,A+N);
    vector<ElementType>B(N,0);
    Count_Sort(TmpA,B);
    for(int i=0;i<N;i++){
        A[i] = B[i];
    }
    TmpA.clear();
    B.clear();
    vector<ElementType>().swap(TmpA);
    vector<ElementType>().swap(B);
}

10.3 桶排序

桶排序.png

描述：

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于
这个映射函数的确定。

我的思路:

对 N 个数据, 建 M 个桶,然后按着数据大小进入桶;

进入每个桶都是链表;

每个桶的数据在进入桶的时候, 从小到大串起来; 大的放后边小的放前面(也可以大的放前边,小的放后边)

然后把桶串起来;

然后 pop 链表, 顺序输出,就是排序好的序列;

复杂度分析

N个数值需要排序, 建立 M 个桶

T(N,M) = O(N+M)

当 N >> M 桶排序
当 M >> N 基数排序

桶排序：将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。

桶排序序思路(github 上那个人写的思路,不是很通俗易懂)：

  1. 设置一个定量的数组当作空桶子。
  2. 寻访序列，并且把项目一个一个放到对应的桶子去。
  3. 对每个不是空的桶子进行排序。
  4. 从不是空的桶子里把项目再放回原来的序列中。
    假设数据分布在[0，100)之间，每个桶内部用链表表示，在数据入桶的同时插入排序，然后把各个桶中的数据合并。
typedef struct LNode *List;//其实是单链表 自己写吧,就不用 STL 里面的了
struct LNode{
    ElementType Data;
    List Next;
    int Length;
    // explicit LNode(int i=0):Data(i),Next(NULL){}
} ListNode;

List initList(){
    List L = (List)malloc(sizeof(struct LNode));
    L->Next = NULL;
    L->Length = 0;
    return L;
}
List insertToList(List L, ElementType data){
    //链表的第一个数据是 L->Next;
    if(L->Next == NULL){
        List Tmp = (List)malloc(sizeof(struct LNode));
        Tmp->Data = data;
        Tmp->Next = NULL;
        L->Next = Tmp;
        L->Length++;
        return L;
    }
   
    if(data<L->Next->Data){
        List Tmp = (List)malloc(sizeof(struct LNode));
        Tmp->Data = data;
        Tmp->Next = L->Next;
        L->Next = Tmp;
        L->Length++;
        return L;
    }
    List Tmp = L;
    while(Tmp->Next!=NULL && data>Tmp->Next->Data){
        Tmp = Tmp->Next;
    }
    if(Tmp->Next==NULL){
        List Tmp2 = (List)malloc(sizeof(struct LNode));
        Tmp2->Data = data;
        Tmp2->Next = NULL;
        Tmp->Next = Tmp2;
        L->Length++;
        return L;
    }else{
        List Tmp2 = (List)malloc(sizeof(struct LNode));
        Tmp2->Data = data;

        Tmp2->Next = Tmp->Next;
        Tmp->Next = Tmp2;
        L->Length++;
        return L;
    }
}
List Merge_List(List L1,List L2){
    if(!L1->Next && !L2->Next){
        return NULL;
    }else if(!L1->Next && L2->Next){
        return L2;
    }else if(L1->Next && !L2->Next){
        return L1;
    }else{
        List Tmp = L1;
        while(Tmp->Next){
            Tmp = Tmp->Next;
        }
        Tmp->Next = L2->Next;
        return L1;
    }
    
}
void bucketSort(ElementType A[],int N){

    //设置桶 M 的大小 这需要提前知道数据特性可以更好设置
    //设置分组间隔
    int space = 10;
    vector<ElementType> TmpA(A,A+N);
    int M =(*max_element(begin(TmpA),end(TmpA)))/space+1;
    //假如最大元素是 99 则桶就是 10
    //假如 A[i]_max = 1000 那么这个数据就放不到我们这支的桶,牺牲空间增加鲁棒性
    List Bucket[M];
    vector<List>BUCKET(M);
    for(int i=0;i<M;i++){
        BUCKET[i] = initList();
    }
    //设置桶深度 数据满足什么条件放入什么桶里面
    
    for(int i= 0;i<N;i++){
        int index = A[i]/space;
        BUCKET[index] = insertToList(BUCKET[index],A[i]);
    }
    //合并桶
    for(int i=0;i<M-1;i++){
        BUCKET[0]= Merge_List(BUCKET[0],BUCKET[i+1]);
    }
    List L = BUCKET[0];
    //将链表数组给到 A 中
    for(int i=0;i<N;i++){
        A[i] = L->Next->Data;
        L = L->Next;
    }
    TmpA.clear();
    BUCKET.clear();
    vector<ElementType>().swap(TmpA);
    vector<List>().swap(BUCKET);
}

10.4 基数排序

基数排序.gif

N 个元素 M 个桶

我的思路

建造 10 个队列 0-9;
先按个位放置从 0 到 9开始进队列 ; 然后按顺序出队列;
再按 10 位放置0 到 9开始进队列进队列; 然后按顺序出队列;
...
按最大位数出队列后 , 则 排序完毕 ;

多关键字排序

比如扑克牌: 用主位优先(Most Signification Digit ) 排序: 为花色建 4 个桶;


扑克基数排序.png

在每个桶分别调用排序算法来解决;结果合并;

次位优先更好一点;
先给面值建立 13 个桶, 再让结果合并, 再给花色建立 4 个桶;

问题: 在任何情况下 LSD 都比 MSD 快吗?
视情况而定把;

/**
 * @brief 基数排序算法
 * 
 * 基数排序：一种多关键字的排序算法，可用桶排序实现。
 * 
 * @param A 
 * @param N 
 */
void radixSortLSD(int A[], int N){
    vector<int>TmpA(A,A+N);
    vector<int>Count(10);
    int max = (*max_element(begin(TmpA),end(TmpA)));

    int times = 1;//进出对列的次数
    int tmp = max/10;
    while(tmp>0){
        times++;
        tmp = tmp/10;
    }
    //求出尾数为 0 - 9 的个数
    //第一次是个位数,第二次是十位数,第三次是百位数
    //我们用 radix 存放
    int radix = 1;
    int index;
    for(int i =0; i<times; i++ ){
        //计数器清
        for(int j=0;j<10;j++){
            Count[j]=0;
        }
        //尾数为 0 的个数为 Count[0]
        //尾数为 1 的个数为 Count[1]
        //...
        for(int j = 0;j<N;j++){
            index = (A[j]/radix)%10;
            Count[index]++;
        }
        for(int j=1;j<10;j++){
            Count[j]=Count[j]+Count[j-1];
        }
       

        for(int j=N-1;j>-1;j--){
            index = (A[j]/radix)%10;
            TmpA[Count[index]-1] = A[j]; 
            Count[index] -- ;
        }
        
        radix = radix * 10;

        //拷贝回去
        for(int j=0;j<N;j++){
            A[j] = TmpA[j];
        }
    }
    Count.clear();
    TmpA.clear();
    vector<int>().swap(Count);
    vector<int>().swap(TmpA);
}

表排序

有带记录

附录: 代码记录

/*
 * @Descripttion: 
 * @version: v_1.0.0
 * @Author: Mailor
 * @Email: xiaolele19980118@163.com
 * @Date: 2020-12-28 17:40:45
 * @LastEditors: Mailor
 * @LastEditTime: 2020-12-30 21:00:16
 */
#include <stdlib.h>
#include<stdio.h>
#include<iostream>
#include<stdbool.h>
#include<vector>
#include<queue>
using namespace std;
typedef int ElementType;

int * bubbleSort(int *a,int length);
void insertSort(int *a , int length);
void shellSort(int A[], int N);
void Merge_Pass(int A[],int TmpA[], int N, int length);
void quickSort(ElementType A[],int N);
void Quick_Sort(ElementType A[], int Left, int Right);
void Count_Sort(vector<int> &A, vector<int> &B);

void swap(int *a, int *b);
void Show_Array(int * p, int len);
void Change_Array(int *p);

void AgeCount(int A[], int N);

void swap(int *a, int *b){
    int tmp ;
    tmp = *a;
    *a = *b;
    *b =  tmp;
}
void swap2(int &a, int &b){
    int tmp = a;
    a = b;
    b = tmp;
}
void Change_Array(int *p)
{
    p[0] = -1; // p[0] == a[0]
}
void Show_Array(int * p, int len)
{
    int i;
    for (i=0; i<len; i++) printf("%d ",p[i]);
    printf("\n");
}
/**
 * @brief 冒泡排序算法
 * 
 * @param a 
 * @param length 
 * @return int* 
 */
int * bubbleSort(int *a, int length){
    for(int i=length-1;i>=0;i--){
        int flag = 0;
        for(int j=0;j<i;j++){
            if(a[j]>a[j+1]){
                swap(&a[j],&a[j+1]);
                flag = 1;
            }
        }
        if(flag == 0){
            break;//无交换 说明有序, 退出循环;
        }
    }
    return a;
}
/**
 * @brief 插入排序算法
 * 
 * @param a 
 * @param length 
 */
void insertSort(int *a , int length){
    for(int i =1;i<length;i++){
        int tmp = a[i];
        int j = 0;
        for(j= i;j>0 && tmp<a[j-1];j--){
            a[j] = a[j-1];
        }
        a[j] = tmp;
    }
}
/**
 * @brief 希尔排序算法
 * 
 * @param A 
 * @param N 
 */
void shellSort(int A[], int N){
    for(int D = N/2; D>0; D = D/2){
        for(int i =D;i<N;i+=D){
                int tmp = A[i];
                int j ;
                for(j=i;j>=D && tmp<A[j-D];j-=D){
                    A[j] = A[j-D];
                }
                A[j] = tmp;
            }
        }
    
}
/**
 * @brief 选择排序算法
 * 
 * @param A 
 * @param index 
 * @param N 
 * @return int 
 */
int ScanForMin(int A[], int index, int N){
    int MinTmp = A[index];
    int position = index;
    for(int i = index; i<N;i++){
        if(A[i]<MinTmp){
            position = i;
            MinTmp = A[i];
        }
    }
    return position;
}

void selectionSort(int A[], int N){
    for(int i = 0; i< N;i++){
        int MinPosition = ScanForMin(A, i, N);
        swap(&A[i],&A[MinPosition]);
    }
   
}
/**
 * @brief 归并排序算法 递归实现
 * 
 * @param A 
 * @param TmpA 
 * @param L 
 * @param R 
 * @param RightEnd 
 */
void Merge(int A[], int TmpA[], int L, int R, int RightEnd){
    int beginIndex = L ;
    int LeftEnd = R -1;
    int i = L;
    while(L<= LeftEnd && R<= RightEnd){
        if(A[L]<=A[R]){
            TmpA[i++] = A[L++];
        }else{
            TmpA[i++] = A[R++];
        }
    }
    while(L <= LeftEnd){
        TmpA[i++] = A[L++];
    }
    while(R <= RightEnd){
        TmpA[i++] = A[R++];
    }
    //TmpA 元素 赋值 给 A
    for(int j = RightEnd;j>=beginIndex;j--){
        A[j] = TmpA[j];
    }

}
void mergeSort(int A[],int TmpA[], int L,int R){
    // int * TmpA = (int *)malloc(sizeof(int)*N) ;
    int Center ;
    if(L<R){
        Center = (L+R)/2+1;
        mergeSort(A,TmpA,L,Center-1);
        mergeSort(A, TmpA,Center,R);
        Merge(A,TmpA,L,Center,R);
    }
}
void mergeSort(int A[], int N){
    int * TmpA = (int * )malloc(sizeof(int)*N);
    if(TmpA != NULL){
        mergeSort(A,TmpA,0,N-1); 
        free(TmpA);    
    }else{
        printf("\n 空间不足 \n");
    }
}
/**
 * @brief 归并排序算法非递归实现
 * 
 * @param A 
 * @param TmpA 
 * @param L 
 * @param R 
 * @param RightEnd 
 */
void Merge1(int A[],int TmpA[],int L,int R,int RightEnd){
    int LeftEnd = R-1;
    int i = L;
    while(L<=LeftEnd && R<=RightEnd){
        if(A[L]<=A[R]){
            TmpA[i++] = A[L++];
        }else{
            TmpA[i++] = A[R++];
        }
    }
    while(L<=LeftEnd){
        TmpA[i++] = A[L++];
    }
    while(R<=RightEnd){
        TmpA[i++] = A[R++];
    }
}
void Merge_Pass(int A[],int TmpA[], int N, int length){
    int i=0;
    for( i=0;i<=N-2*length;i+=2*length){
        Merge1(A,TmpA,i,i+length,i+2*length-1);
    }
    if(i+length<N){
        Merge1(A,TmpA,i,i+length,N-1);
    }else{
        for(int j=i;j<N;j++){
            TmpA[j] = A[j];
        }
    }
}
void MergeSort2(int A[],int N){
    int * TmpA = (int *)malloc(sizeof(int)*N);
    if(TmpA!=NULL){
        int length = 1;
        while(length<N){
            Merge_Pass(A,TmpA,N,length);
            length*=2;
            Merge_Pass(TmpA,A,N,length);
            length*=2;
        }
        free(TmpA);
    }else{
        printf("\n 内存分配失败;\n");
        exit(0);
    }
}

/**
 * @brief 快速排序算法
 * 
 * @param argc 
 * @param argv 
 * @return int 
 */
#define CUT_OFF 1e5 //定义一个阈值,因为数据元素不是很多时候,插排比快排好
//主元
ElementType Median3(ElementType A[],int Left, int Right){
    int Center = (Left + Right)/2 + 1;
    if(A[Left]>A[Center]){swap(&A[Left],&A[Center]);}
    if(A[Left]>A[Right]){swap(&A[Left],&A[Right]);}
    if(A[Right]>A[Center]){swap(&A[Right],&A[Center]);}

    swap(&A[Center],&A[Right-1]);
    return A[Right-1];
}
void Quick_Sort(ElementType A[], int Left, int Right){
    if(Right-Left>CUT_OFF){
        ElementType Pivot = Median3(A,Left, Right);
        int i = Left;
        int j = Right-1;
        for(;;){
            while(A[++i]<Pivot){}
            while(A[--j]>Pivot){}
            if(i<j){
                swap(&A[i],&A[j]);
            }else{
                // swap(&A[j],&A[Right-1]);
                break;
            }
        }
        swap(&A[i],&A[Right-1]);
        Quick_Sort(A,Left,i-1);
        Quick_Sort(A,i+1,Right);

    }else{
        selectionSort(A+Left,Right-Left+1);
    }
}
void quickSort(ElementType A[],int N){
    Quick_Sort(A,0,N-1);
}

/**
 * @brief 统计年龄:人数
 * 
 * 比如给出数组 [20,20,22,22,20,20,23,23,23,45]
 * 输出结果应该是
 * 20:4
 * 22:2
 * 23:3
 * 45:1
 * 
 */

void AgeCount(vector<int>& A){
    int N = A.size();
    int max = (*max_element(begin(A),end(A)));
     printf("\n%d\t\n",max);
    vector<int> TmpA(max+1,0);;//由于 0 的特殊性
    for(int i=0;i<N;i++){
        TmpA[A[i]]++;
    }
    for(int i=0;i<max+1;i++){
        // printf("%d\t", TmpA[i]);
        if(TmpA[i]!=0){
            printf("\n%d %d",i,TmpA[i]);
            cout<<endl;
        }
    }
}
   

/**
 * @brief 计数排序算法
 * 
 * @param A 
 * @param B 
 */
void countSort(ElementType A[], int N){
    vector<ElementType>TmpA(A,A+N);
    vector<ElementType>B(N,0);
    Count_Sort(TmpA,B);
    for(int i=0;i<N;i++){
        A[i] = B[i];
    }
    TmpA.clear();
    B.clear();
    vector<ElementType>().swap(TmpA);
    vector<ElementType>().swap(B);
}
void Count_Sort(vector<int> &A, vector<int> &B){
 
    if(A.size() == 0){
        return ;
    }
    int max = (*max_element(begin(A),end(A)));//最大元素
    vector<int> CountA(max+1,0);

    for(int i = 0;i<A.size();i++){
        CountA[A[i]]++;
    }
    int k = 0;
    for(int i= 0;i<max+1;i++){
        if(CountA[i]!=0){
            //  打印统计的个数
            //  printf("\n%d %d",i,CountA[i]);
            for(int j=0;j<CountA[i];j++){
                B[k++] = i;
            }
        }
    }
}

/**
 * @brief 通排序算法
 * 
 * @param argc 
 * @param argv 
 * @return int 
 */

typedef struct LNode *List;//其实是单链表 自己写吧,就不用 STL 里面的了
struct LNode{
    ElementType Data;
    List Next;
    int Length;
    // explicit LNode(int i=0):Data(i),Next(NULL){}
} ListNode;

List initList(){
    List L = (List)malloc(sizeof(struct LNode));
    L->Next = NULL;
    L->Length = 0;
    return L;
}
List insertToList(List L, ElementType data){
    //链表的第一个数据是 L->Next;
    if(L->Next == NULL){
        List Tmp = (List)malloc(sizeof(struct LNode));
        Tmp->Data = data;
        Tmp->Next = NULL;
        L->Next = Tmp;
        L->Length++;
        return L;
    }
   
    if(data<L->Next->Data){
        List Tmp = (List)malloc(sizeof(struct LNode));
        Tmp->Data = data;
        Tmp->Next = L->Next;
        L->Next = Tmp;
        L->Length++;
        return L;
    }
    List Tmp = L;
    while(Tmp->Next!=NULL && data>Tmp->Next->Data){
        Tmp = Tmp->Next;
    }
    if(Tmp->Next==NULL){
        List Tmp2 = (List)malloc(sizeof(struct LNode));
        Tmp2->Data = data;
        Tmp2->Next = NULL;
        Tmp->Next = Tmp2;
        L->Length++;
        return L;
    }else{
        List Tmp2 = (List)malloc(sizeof(struct LNode));
        Tmp2->Data = data;

        Tmp2->Next = Tmp->Next;
        Tmp->Next = Tmp2;
        L->Length++;
        return L;
    }
}
List Merge_List(List L1,List L2){
    if(!L1->Next && !L2->Next){
        return NULL;
    }else if(!L1->Next && L2->Next){
        return L2;
    }else if(L1->Next && !L2->Next){
        return L1;
    }else{
        List Tmp = L1;
        while(Tmp->Next!=NULL){
            Tmp = Tmp->Next;
        }
        Tmp->Next = L2->Next;
        L1->Length =L1->Length+L2->Length;
        return L1;
    }
    
}
void bucketSort(ElementType A[],int N){

    //设置桶 M 的大小 这需要提前知道数据特性可以更好设置
    //设置分组间隔
    int space = 10;
    vector<ElementType> TmpA(A,A+N);
    int M =(*max_element(begin(TmpA),end(TmpA)))/space+1;
    //假如最大元素是 99 则桶就是 10
    //假如 A[i]_max = 1000 那么这个数据就放不到我们这支的桶,牺牲空间增加鲁棒性
    // List Bucket[M];//用这个也行
    vector<List>BUCKET(M);
    for(int i=0;i<M;i++){
        BUCKET[i] = initList();
    }
    //设置桶深度 数据满足什么条件放入什么桶里面
    
    for(int i= 0;i<N;i++){
        int index = A[i]/space;
        BUCKET[index] = insertToList(BUCKET[index],A[i]);
    }
    //合并桶
    for(int i=0;i<M-1;i++){
        BUCKET[0]= Merge_List(BUCKET[0],BUCKET[i+1]);
    }
    List L = BUCKET[0];
    //将链表数组给到 A 中
    for(int i=0;i<N;i++){
        A[i] = L->Next->Data;
        L = L->Next;
    }
    TmpA.clear();
    BUCKET.clear();
    vector<ElementType>().swap(TmpA);
    vector<List>().swap(BUCKET);
}

// 基数排序：一种多关键字的排序算法，可用桶排序实现。


/**
 * @brief 基数排序算法
 * 
 * 基数排序：一种多关键字的排序算法，可用桶排序实现。
 * 
 * @param A 
 * @param N 
 */
void radixSortLSD(int A[], int N){
    vector<int>TmpA(A,A+N);
    vector<int>Count(10);
    int max = (*max_element(begin(TmpA),end(TmpA)));

    int times = 1;//进出对列的次数
    int tmp = max/10;
    while(tmp>0){
        times++;
        tmp = tmp/10;
    }
    //求出尾数为 0 - 9 的个数
    //第一次是个位数,第二次是十位数,第三次是百位数
    //我们用 radix 存放
    int radix = 1;
    for(int i =0; i<times; i++ ){
        //计数器清
        for(int j=0;j<10;j++){
            Count[j]=0;
        }
        //尾数为 0 的个数为 Count[0]
        //尾数为 1 的个数为 Count[1]
        //...
        for(int j = 0;j<N;j++){
            Count[A[j]/radix%10]++;
            // int index = (A[j]/radix)%10;
            // Count[index]++;
        }
        for(int j=1;j<10;j++){
            Count[j]=Count[j]+Count[j-1];
        }
       

        for(int j=N-1;j>-1;j--){
            TmpA[--Count[A[j]/radix%10]] = A[j];//合成一行代码
            // int index = (A[j]/radix)%10;
            // TmpA[Count[index]-1] = A[j]; 
            // Count[index] -- ;
        }
        
        radix = radix * 10;

        //拷贝回去
        for(int j=0;j<N;j++){
            A[j] = TmpA[j];
        }
    }
    Count.clear();
    TmpA.clear();
    vector<int>().swap(Count);
    vector<int>().swap(TmpA);
}

int main(int argc, char * argv[]){

    int a[10] ={12,1,5,34,35,3,6, 20,12,12};
    Show_Array(a,10);
   
//--------------------------------

    //change Array 测试
    // int *p = bubbleSort(a, 10);
    // Change_Array(a);
    
//--------------------------------
    // 插入排序测试
    // insertSort(a,10);
    // Show_Array(a,10);
//--------------------------------

    // 希尔排序测试
    // shellSort(a,10);
    // Show_Array(a,10);
    
//--------------------------------
    //选择排序测试
    // selectionSort(a,10);
    // Show_Array(a,10);

//--------------------------------
    // 归并排序递归测试
    // mergeSort(a,10);
    // Show_Array(a,10);

    // 归并排序非递归测试
    // MergeSort2(a,10);
    // Show_Array(a,10);
//--------------------------------
    // 快速排序测试
    // quickSort(a,10);
    // Show_Array(a,10);
    
 //--------------------------------   
    // 计数排序测试
    // countSort(a,10);  
    // Show_Array(a,10);
//--------------------------------   
    //桶排序函数测试
    // 插入链表测试
    // List L[2];
    // L[1]= initList();
    // L[1] = insertToList(L[1],35);
    // L[1] = insertToList(L[1],21);
    // L[1] = insertToList(L[1],34);

    // //合并链表测试
    // L[0] = initList();
    // L[0] = insertToList(L[0],54);
    // L[0] = insertToList(L[0],52);
    // L[0] = insertToList(L[0],51);

    // L[1] = Merge_List(L[1],L[0]);
    // while(L[1]->Next){
    //     printf("\nnew L[1]= %d\t",L[1]->Next->Data);
    //     L[1] = L[1]->Next;
    // }
    // cout<<endl;

    // //通排序算法测试 
    // bucketSort(a,10);
    // Show_Array(a,10);
//--------------------------------

    //基数排序测试
    radixSortLSD(a,10);
    Show_Array(a,10);
//--------------------------------


    // int xx = 6;
    // int yy = 5;
    // xx = xx>>3;
    // swap2(xx,yy);
    // cout<<yy<<endl;
//--------------------------------
    //vector push pop 测试
    // int b[10] = {20,20,22,22,20,20,23,23,23,45};
    // vector<int>B(b,b+10);
    // B.push_back(100);
    // for(int i=0;i<B.size();i++){
    //     printf("\nB = %d",B[i]);
    // }
    // AgeCount(B);

    return 0;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 202,980评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,178评论 2赞 380
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 149,868评论 0赞 336
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,498评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,492评论 5赞 364
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,521评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,910评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,569评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,793评论 1赞 296
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,559评论 2赞 319
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,639评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,342评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,931评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,904评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,144评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,833评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,350评论 2赞 342

推荐阅读更多精彩内容