我自己认为比较难得排序算法都完成了代码，包含插入排序、快速排序、堆排序、归并排序

希尔排序、冒泡排序、简单选择排序的原理都很简单，代码暂时留着到有时间的时候补回来。

基数排序中涉及链表比较麻烦，补代码的可能性不大（笑哭）

对于外部排序应该是没有办法写代码吧，主要应该就是理解败者树和置换—选择排序，个人感觉

• 内部排序

  • 稳定排序算法

    • 插入排序：时间复杂度：O(N*N)

    • 冒泡排序：时间复杂度：O(N*N)

    • 归并排序：时间复杂度：O(N*log2(N))

    • 基数排序：时间复杂度：O(d(n+r))

  • 不稳定排序算法

    • 希尔排序：时间复杂度：O(n的1.3次方)->O(N*N)

    • 快速排序：时间复杂度：O(N*log2(N))

    • 简单选择排序：时间复杂度：O(N*N)

    • 堆排序：时间复杂度：O(N*log2(N))

• 外部排序

  • 优化方法：

    • 多路归并——败者树

    • 减少初始归并段数量——置换—选择排序

目录

1、插入排序

1.1 算法思想

1.2 算法性能

1.3 算法代码

2 希尔排序

2.1 算法思想

2.2 算法性能

2.3 算法代码

3 冒泡排序

3.1 算法思想

3.2 算法性能

3.3 算法代码

4 快速排序

4.1 算法思想

4.2 算法性能

4.3 算法代码

5 简单选择排序

5.1 算法思想

5.2 算法性能

5.3 算法代码

6 堆排序

6.1 算法思想

6.2 算法性能

6.3 算法代码

7 归并排序

7.1 算法思想

7.2 算法性能

7.3 算法代码

8 基数排序

8.1 算法思想

8.2 算法性能

9 外部排序

9.1 败者树

9.2 置换—选择排序

9.3 最佳归并树

1、插入排序

1.1 算法思想

没次将一个待排序的记录按其关键字大小插入到前面已经排好了的子序列中，直到全部记录插入完成

1.2 算法性能

1. 空间复杂度：O（1）

2. 时间复杂度：O(n*n）

3. 稳定排序

1.3 算法代码

 #include<stdio.h>
 #include<stdlib.h>
 #include<time.h>
 ​
 void PrintSort(int a[],int n){  //打印当前的数组序列 
     for(int i=0;i<n;i++)
         printf("%d ",a[i]);
     printf("\n");
 }
 ​
 void InsertSort(int a[],int n){ //插入排序 
     int j; 
     for(int i=1;i<n;++i) //从第二个元素开始往下寻找左边有比自己小的元素 
     {
         int temp = a[i];    //保存当前的元素值，以防移动中被覆盖掉 
         for(j=i-1;j>=0 && a[j]>temp;j--)    
             a[j+1]=a[j];    //将左边的元素右移 
         a[j+1]=temp;        //移动元素归位 
         if(i<n-1) printf("第%d个元素排序后的结果：",i);
         else if(i==n-1) printf("最终的排序结果为：");  
         PrintSort(a,n);
     }
 }
 int main(){
     
     srand((unsigned)(time(NULL)));  //调用srand函数，让rand函数没次使用不同的随机数种子，保证每次产生的随机数不相同。 
     int a[100];
     int n;
     
     printf("请输入需要产生随机数的个数:"); 
     scanf("%d",&n); //n<100 
     
     for(int i=0;i<n;i++) //产生n个随机数在数组a内 
         a[i]=rand()%100;    //保证数组元素大小在0到99以内 
     printf("产生的随机数组为："); 
     PrintSort(a,n);     //打印初始数组元素 
         
     InsertSort(a,n); //插入排序 
     
     return 0; 
 } 

2 希尔排序

2.1 算法思想

先将待排序表分割成若干形如L[i,i+d,i+2d ...... i+kd]的“特殊“子表，对各个子表分别进行直接插入排序缩小增量d，重复上述过程，直到d=1为止

2.2 算法性能

1. 空间复杂度：O(1)

2. 时间复杂度：O(n的1.3次方)

3. 不稳定排序

2.3 算法代码

3 冒泡排序

3.1 算法思想

从后往前（或者从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]）则交换他们，直到序列比较完

3.2 算法性能

1. 时间复杂度：O(n*n)

2. 空间复杂度：O(1)

3. 稳定排序

3.3 算法代码

4 快速排序

4.1 算法思想

快速排序算法思想：算法思想:在待排序表L1..n]中任取一个元素pivot作为枢轴(或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分L[1..k-1]和L[k+1...n]，使得L1...k-1]中的所有元素小于pivot，Llk+1..n]中的所有元素大于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

4.2 算法性能

1. 时间复杂度：最好O（nlogn）最坏O(n*n)

2. 空间复杂度：最好O（nlogn）最坏O(n*n)

3. 当待排序序列正序或逆序，空间和时间复杂度最高

4. 不稳定排序

4.3 算法代码

 #include<stdio.h>
 #include<stdlib.h>
 #include<time.h>
 ​
 int NQuickSort;  //快速排序的数组元素数量 
 ​
 void PrintSort(int a[],int n){  //打印当前的数组序列 
     for(int i=0;i<n;i++)
         printf("%d ",a[i]);
     printf("\n");
 }
 ​
 void QuickSort(int a[],int l,int r) {
     
     if(r<=l) return;    //如果当前数组不需要进行排序 
     else printf("%d %d\n",l,r);
     int left=l,right=r;
     int first=a[left];
     while(left < right){
         while(left < right && a[right] >= first) right--;
         a[left]=a[right];
         while(left < right && a[left] <= first) left++;
         a[right]=a[left];
     }
     a[left]=first;
     
     PrintSort(a,NQuickSort);
     
     int mid = left;
     PrintSort(a,NQuickSort);
     QuickSort(a,l,mid-1);
     QuickSort(a,mid+1,r);
 }
 int main(){
     
     srand((unsigned)(time(NULL)));  //调用srand函数，让rand函数没次使用不同的随机数种子，保证每次产生的随机数不相同。 
     int a[100];
     int n;
     
     printf("请输入需要产生随机数的个数:"); 
     scanf("%d",&NQuickSort); //n<100 
     
     for(int i=0;i<NQuickSort;i++) //产生n个随机数在数组a内 
         a[i]=rand()%100;    //保证数组元素大小在0到99以内 
     printf("产生的随机数组为："); 
     PrintSort(a,NQuickSort);        //打印初始数组元素 
         
     QuickSort(a,0,NQuickSort-1);
     
     return 0; 
 } 

5 简单选择排序

5.1 算法思想

每一趟再待排序元素中选取关键字最小的元素加入有序子列

5.2 算法性能

1. 空间复杂度：O（1）

2. 时间复杂度：O（n*n）

3. 不稳定排序

5.3 算法代码

5 简单选择排序

6 堆排序

6.1 算法思想

1. 若满足任意根节点元素值大于左右节点——大根堆

2. 若满足任意根节点元素值小于左右节点——小根堆

6.2 算法性能

1. 空间复杂度：O（1）

2. 时间复杂度：O（n*n）

3. 不稳定排序

6.3 算法代码

1. 大根堆创建代码

 #include<stdio.h>
 #include<stdlib.h>
 #include<time.h>
 int a[100];
 ​
 void PrintSort(int n){  //打印当前的数组序列 
     for(int i=1;i<=n;i++)
         printf("%d ",a[i]);
     printf("\n");
 }
 void swap(int i,int n){
     if(i*2>n) return;
     //printf("%d**\n",i);
     int j;
     if(a[i]<a[2*i] && a[i]<a[2*i+1] && 2*i+1<=n){   //如果左右孩子都大于根节点 
         if(a[2*i]>a[2*i+1]) j=2*i;  //为根节点找到左右孩子中较大下标 
         else j=2*i+1;
         a[0]=a[i];a[i]=a[j];a[j]=a[0];
         swap (j,n); //递归修复刚刚交换过的节点，防止交换改变结构 
     }
     else if(a[i]<a[2*i]){   //如果左孩子大于根节点 
         a[0]=a[i];a[i]=a[2*i];a[2*i]=a[0];
         swap(2*i,n);
     }
     else if(a[i]<a[2*i+1] && 2*i+1<=n){ //如果右孩子大于根节点 
         a[0]=a[i];a[i]=a[2*i+1];a[2*i+1]=a[0];
         swap(2*i+1,n);
     }
     //PrintSort(n); //打印没次变动后的序列 
     
 }
 void SetMaxHeap(int n){
     for(int i=n/2;i>0;i--){
         swap(i,n);
     }
 } 
 void HeapSort(int n){
     for(int i=1;i<n;i++){
         int temp=a[1];a[1]=a[n-i+1];a[n-i+1]=temp;//将堆顶元素与堆尾元素交换 
         printf("找到%d个顶：",i); 
         PrintSort(n);
         swap(1,n-i);    //重新构建大顶堆 
     }
 } 
 ​
 int main(){
     
     srand((unsigned)(time(NULL)));  //调用srand函数，让rand函数没次使用不同的随机数种子，保证每次产生的随机数不相同。 
     int n;
     printf("请输入需要产生随机数的个数:"); 
     scanf("%d",&n); //n<100 
     
     for(int i=1;i<=n;i++) //产生n个随机数在数组a内 
         a[i]=rand()%100;    //保证数组元素大小在0到99以内
         
 //  for(int i=1;i<=n;i++)   //测试错误样例 
 //      scanf("%d",&a[i]);
 //       
     printf("产生的随机数组为："); 
     PrintSort(n);       //打印初始数组元素 
         
     SetMaxHeap(n);  //创建大根堆 
     printf("创建大根堆后数组顺序为："); PrintSort(n);
     
     HeapSort(n);    //对创建的大根堆进行排序 
     printf("排序完成后的数组序列为："); PrintSort(n);
     
     return 0; 
 } 

7 归并排序

7.1 算法思想

• 把两个或多个已经有的序列合并为一个序列

7.2 算法性能

1. 时间复杂度：O（n*logn）

2. 空间复杂度：O（n）

3. 稳定排序

7.3 算法代码

 #include<stdio.h>
 #include<stdlib.h>
 #include<time.h>
 ​
 int a[100];
 int m;
 void PrintSort(int n){  //打印当前的数组序列 
     for(int i=0;i<n;i++)
         printf("%d ",a[i]);
     printf("\n");
 }
 ​
 void MergerPrint(int left,int right,int n){
     for(int i=0;i<n;i++){
         if(left==i || right==i) printf(" ** ");
         printf("%d ",a[i]);
     }
         
     printf("\n");
 }
 ​
 void Merge(int left,int mid,int right){
     int b[100];
     int i,j,k;
     
     for(i=left;i<=right;i++)    //将数组a的待排序部分复制到临时数组B中 
         b[i]=a[i];
     
     for(i=left,j=mid+1,k=i;i<=mid&&j<=right;k++){   //进行归并 
         if(b[i]<=b[j]) a[k]=b[i++];
         else  a[k]=b[j++];
     }
     while(i<=mid) a[k++]=b[i++];
     while(j<=right) a[k++]=b[j++];
 }
 ​
 void MergeSort(int left,int right){
     if(right<=left) return;
     int mid=(left+right)/2;
     MergeSort(left,mid);    //对左半部分进行归并 ——递归 
     MergeSort(mid+1,right); //对右半部分进行归并 ——递归 
     Merge(left,mid,right);  //对当前部分进行归并 
     
 //  MergerPrint(left,right,m); //查看归并排序过 
 } 
 ​
 int main(){
     
     srand((unsigned)(time(NULL)));  //调用srand函数，让rand函数没次使用不同的随机数种子，保证每次产生的随机数不相同。 
     
     int n;
     
     printf("请输入需要产生随机数的个数:"); 
     scanf("%d",&n); //n<100 
     m=n;
     for(int i=0;i<n;i++) //产生n个随机数在数组a内 
         a[i]=rand()%100;    //保证数组元素大小在0到99以内 
     printf("产生的随机数组为："); 
     PrintSort(n);       //打印初始数组元素 
         
     MergeSort(0,n-1);
     printf("最终排序结果为："); 
     PrintSort(n);
     return 0; 
 } 

8 基数排序

8.1 算法思想

• 先对位权较小的部分进行排序

1. 第一趟以个位递减排列的序列

2. 第一趟以十位递减排列的序列

3. 第一趟以百位递减排列的序列

8.2 算法性能

1. 时间复杂度：O（d（n+r））

2. 空间复杂度：O（r）

3. 稳定排序

4. 基数排序主要解决的问题

   • 数据元素的关键字可以方便地拆分为d组，且d较小

   • 每组关键字的取值范围不大，即r较小

   • 数据元素个数n较大

9 外部排序

• 概念：数据元素太多，无法一次性全部读入内存进行排序

• 实现方法：使用归并排序，最多只需要在内存中分配3块大小相同的缓冲区即可，对任意一个大文件进行排序

• 时间开销分析：外部排序——生成初始化归并段——第一趟归并——第二趟归并——第三趟归并

• 外部排序时间开销=读写外存的时间+内部排序时间+内部归并所需时间

• 优化方法：

  • 多路归并——败者树

  • 减少初始归并段数量——置换—选择排序

9.1 败者树

• 用败者树，选择出最小元素，只需对比关键字log以2为底的k次方

• 

9.2 置换—选择排序

设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳w个记录。置换-选择算法的步骤如下:

1. 从FI输入w个记录到工作区WA。

2. 从WA中选出其中关键字取最小值的记录，记为MINIMAX记录。

3. 将MINIMAX记录输出到FO中去。

4. 若FI不空，则从FI输入下一个记录到WA中。

5. 从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。

6. 重复3)~5)，直至在WA中选不出新的MINIMAX记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去。

7. 重复2)~6)，直至WA为空。由此得到全部初始归并段。

9.3 最佳归并树

• 对于k叉归并，若初始归并段的数量无法构成严格的k叉归并树，则需要补充n和长度为0的虚根，再进行k叉哈夫曼树的构造

• 补几个问题

  1. （初始归并段数量-1）%（k-1)=0 不需要补虚根

  2. （初始归并段数量-1）%（k-1)=u 需要补（k-1)-u个虚根