C语言程序设计教程（第三版）课后习题7.2 （C++代码）

解题思路:

多种排序详解

注意事项:

参考代码:

1.插排

//直接插入排序是一种最简单的排序方法，
//它的基本操作是将一个记录插入到已经排好序的有序表中，
//从而得到一个新的且记录数增加了1的有序表。
#include <iostream>
#include <iomanip>
// 分类 ------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
// 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
using namespace std;
  void swap(int &x, int &y)
  {
     int temp = x;
      x = y;
       y = temp;
  }
   void insertion(int a[], int sz)
    {
      for(int i=1;i<=sz;i++) {
       int j=i;
        while(j>0&&(a[j]<a[j-1])) {
          swap(a[j],a[j-1]);
           j--;
        }
    }
}
   int main()
     {
       int a[10005],n;
         scanf("%d",&n);
           for(int i=1;i<=n;i++)
             scanf("%d",&a[i]);
               insertion(a,n);
    for(int i=1;i<=n;i++)
     {
        printf("%d ",a[i]);
	 } 
}

2.归排

//归并排序是基于归并操作完成的，
//而一次归并操作是通过两个或两个以上的有序表
//合并成一个新的有序表完成的。
//常见的归并排序是2-路归并排序，
//其核心操作是将一维数组中前后相邻的两个有序序列
//归并成一个有序序列。 
#include<iostream>
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(n)
// 稳定性 ------------ 稳定
using namespace std;
 const int SIZE = 100;
  int arr[SIZE];
   int rec[SIZE];
     void merge(int fir,int end,int mid);
       int pass(int n);
         void mergeSort3(int n);
           void mergeSort3(int n){
             int num=pass(n);
    while(num!=2)
	{
        for(int i=0;i<num;i+=2)
            merge(rec[i],rec[i+2]-1,rec[i+1]-1);
        num=pass(n);
    }
}
void merge(int fir,int end,int mid){
    int tempArr[SIZE];
      int fir1=fir,fir2=mid+1;
        for(int i=fir;i<=end;i++){
          if(fir1>mid)
            tempArr[i]=arr[fir2++];
        else if(fir2>end)
            tempArr[i]=arr[fir1++];
        else if(arr[fir1]>arr[fir2])
            tempArr[i]=arr[fir2++];
        else 
            tempArr[i]=arr[fir1++];
    }
    for(int i=fir;i<=end;i++)
        arr[i]=tempArr[i];
}
int pass(int n){
     int num=0;
      int biger=arr[0];
       rec[num++]=0;
        for(int i=1;i<n;i++){
          if(arr[i]>=biger)biger=arr[i];
        else 
		{
            rec[num++]=i;
            biger=arr[i];
        }
    }
     rec[num++]=n;
    return num;
}
int main(){
     int n;
   	  cin>>n;
        for(int i=0;i<n;i++)cin>>arr[i];
         mergeSort3(n);
          for(int i=0;i<n;i++)cout<<arr[i]<<" ";
           cout<<endl;
}

3.快排

//快速排序是对起泡排序的一种改进。
//它的基本思想是，
//通过一趟排序将待排序的记录分割成两个独立的部分，
//其中一部分记录的关键字均比另一部分的关键字小，
//在分成两个部分之后则可以分别对这两个部分继续进行排序，
//从而使整个序列有序。
#include <cstdio>
#include <algorithm>
#include <queue>//头文件
// 分类 ------------ 内部比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
// 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)       
// 稳定性 ---------- 不稳定
using namespace std;
const int maxx = 100000 + 10;
int Heap[maxx];
int main()
{
    int n,num = 0,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&x),Heap[++num]=x,push_heap(Heap+1,Heap+num+1,greater<int>());
    for(int i=1;i<=n;i++)
            printf("%d ",Heap[1]),pop_heap(Heap+1,Heap+num+1,greater<int>()),num--;
            return 0;
}

4.选排

//选择排序的基本思想是：
//每一趟比较过程中，
//在n-i+1(i=1,2,...,n-1)
//个记录中选取关键字最小的记录作为有序序列中的第i个记录。
//在多种选择排序中，
//最常用且形式最为简单的是简单选择排序。
#include<cstdio>
#include<iostream>
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(n^2)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
using namespace std;
int main()
{
	int n;
	 scanf("%d",&n);
	   int a[10005];
	     for(int i=1;i<=n;i++)
	        {
		      scanf("%d",&a[i]);
	        }
	     for(int i=1;i<n;i++)
            {
              int min=i;
               for (int j=i+1;j<n+1;j++)
                   {
                      if(a[j]<a[min])
                       min=j;
                   }
                swap(a[i],a[min]);
            }
	    for(int i=1;i<=n;i++)
	        printf("%d ",a[i]);  
}