插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序

插入排序方法：时间复杂度O(n^2)的稳定排序： 每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。 直接插入排序的算法思路： （1） 设置监视哨r[0]，将待插入纪录的值赋值给r[0]； （2） 设置开始查找的位置j； （3） 在数组中进行搜索，搜索中将第j个纪录后移，直至r[0].key≥r[j].key为止； （4） 将r[0]插入r[j+1]的位置上。 代码：void Insert_sort(int n)          {         /* 对数组R中的记录R[1..n]按递增序进行插入排序  */ int i,j; for(i=2;i<=n;i++) /* 依次插入R[2]，…，R[n] */     if(R[i]<R[i-1])     {/* 若R[i]大于等于有序区中所有的R，则R[i] */         /* 应在原有位置上 */         R[0]=R[i];j=i-1; /* R[0]是哨兵，且是R[i]的副本 */         do{ /* 从右向左在有序区R[1．．i-1]中查找R[i]的插入位置 */             R[j+1]=R[j]; /* 将关键字大于R[i]的记录后移 */             j--;         }while(R[0]<R[j]);  /* 当R[i]≥R[j]时终止 */         R[j+1]=R[0]; /* R[i]插入到正确的位置上 */     }           } 希尔排序法(缩小增量排序)：时间复杂度与增量序列的选取有关，下限是n*log2n不稳定排序 代码：     void ShellPass(int d, int n) {/* 希尔排序中的一趟排序，d为当前增量 */     int i,j;     for(i=d+1;i<=n;i++) /* 将R[d+1．．n]分别插入各组当前的有序区 */         if(R[i]<R[i-d])         {             R[0]=R[i];j=i-d; /* R[0]只是暂存单元，不是哨兵 */             do {/* 查找R[i]的插入位置 */                 R[j+d]=R[j];/* 后移记录 */                 j=j-d; /* 查找前一记录 */             }while(j>0&&R[0]<R[j]);             R[j+d]=R[0]; /* 插入R[i]到正确的位置上 */         } /* endif */ } /* end of ShellPass */ void  Shell_Sort(int n) {     int increment=n; /* 增量初值，不妨设n>0 */     do {         increment=increment/3+1; /* 求下一增量 */         ShellPass(increment,n); /* 一趟增量为increment的Shell插入排序 */     }while(increment>1); } /* ShellSort */ 冒泡排序法 void Bubble_sort(int n) {     int i,j;     int exchange; /* 交换标志 */     for(i=1;i<n;i++){ /* 最多做n-1趟排序 */         exchange=0; /* 本趟排序开始前，交换标志应为假 */         for(j=n-1;j>=i;j--) /* 对当前无序区R[i..n]自下向上扫描 */             if(R[j+1]<R[j]){/* 交换记录 */                 R[0]=R[j+1]; /* R[0]不是哨兵，仅做暂存单元 */                 R[j+1]=R[j];                 R[j]=R[0];                 exchange=1; /* 发生了交换，故将交换标志置为真 */             }             if(!exchange) /* 本趟排序未发生交换，提前终止算法 */                 return;     } } 快速排序法平均复杂度O(nlgn)，不是稳定排序 基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列 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-完成的时候，此时令循环结束）。 代码： int Partition(int i,int j) {/* 调用Partition(R，low，high)时，对R[low..high]做划分，*/     /* 并返回基准记录的位置 */     int pivot=R[i]; /* 用区间的第1个记录作为基准 */     while(i<j){ /* 从区间两端交替向中间扫描，直至i=j为止 */         while(i<j&&R[j]>=pivot) /* pivot相当于在位置i上 */             j--;  /* 从右向左扫描，查找第1个关键字小于pivot.key的记录R[j] */         if(i<j) /* 表示找到的R[j]的关键字<pivot.key  */             R[i++]=R[j]; /* 相当于交换R[i]和R[j]，交换后i指针加1 */         while(i<j&&R[i]<=pivot) /* pivot相当于在位置j上*/             i++; /* 从左向右扫描，查找第1个关键字大于pivot.key的记录R[i] */         if(i<j) /* 表示找到了R[i]，使R[i].key>pivot.key */             R[j--]=R[i]; /* 相当于交换R[i]和R[j]，交换后j指针减1 */     } /* endwhile */     R[i]=pivot; /* 基准记录已被最后定位*/     return i; } /* end of partition  */ void Quick_Sort(int low,int high) { /* 对R[low..high]快速排序 */     int pivotpos; /* 划分后的基准记录的位置 */     if(low<high){/* 仅当区间长度大于1时才须排序 */         pivotpos=Partition(low,high); /* 对R[low..high]做划分 */         Quick_Sort(low,pivotpos-1); /* 对左区间递归排序 */         Quick_Sort(pivotpos+1,high); /* 对右区间递归排序 */     } } /* end of Quick_Sort */ 选择排序法 void Select_Sort(int n) {     int i,j,k;     for(i=1;i<n;i++)     {/* 做第i趟排序(1≤i≤n-1) */         k=i;         for(j=i+1;j<=n;j++) /* 在当前无序区R[i..n]中选key最小的记录R[k] */             if(R[j]<R[k])                 k=j; /* k记下目前找到的最小关键字所在的位置 */         if(k!=i)         { /* 交换R[i]和R[k] */             R[0]=R[i]; R[i]=R[k]; R[k]=R[0]; /* R[0]作暂存单元 */         } /* endif */     } /* endfor */ } /* end of Select_Sort */ 堆排序法(完全二叉树) void Heapify(int s,int m) { /*对R[1..n]进行堆调整，用temp做暂存单元 */     int j,temp;     temp=R[s];     j=2*s;     while (j<=m)     {         if (R[j]>R[j+1]&&j<m) j++;         if (temp<R[j]) break;         R[s]=R[j];         s=j;         j=j*2;     }/* end of while */     R[s]=temp; } /* end of Heapify */ void BuildHeap(int n) { /* 由一个无序的序列建成一个堆 */     int i;     for(i=n/2;i>0;i--)         Heapify(i,n); } void Heap_Sort(int n) { /* 对R[1..n]进行堆排序，不妨用R[0]做暂存单元 */     int i;     BuildHeap(n); /* 将R[1-n]建成初始堆 */     for(i=n;i>1;i--)     { /* 对当前无序区R[1..i]进行堆排序，共做n-1趟。 */         R[0]=R[1]; R[1]=R[i];R[i]=R[0]; /* 将堆顶和堆中最后一个记录交换 */         Heapify(1,i-1); /* 将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质 */     } /* end of for */ } /* end of Heap_Sort */ 归并排序(稳定排序) 归并操作的工作原理如下： 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针超出序列尾 将另一序列剩下的所有元素直接复制到合并序列尾 void Merge(int low,int m,int high) {/* 将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的 */     /* 子文件R[low..high] */     int i=low,j=m+1,p=0; /* 置初始值 */     int *R1; /* R1是局部向量，若p定义为此类型指针速度更快 */     R1=(int *)malloc((high-low+1)*sizeof(int));     if(!R1) /* 申请空间失败 */     {         puts("Insufficient memory available!");         return;     }     while(i<=m&&j<=high) /* 两子文件非空时取其小者输出到R1[p]上 */         R1[p++]=(R[i]<=R[j])?R[i++]:R[j++];     while(i<=m) /* 若第1个子文件非空，则复制剩余记录到R1中 */         R1[p++]=R[i++];     while(j<=high) /* 若第2个子文件非空，则复制剩余记录到R1中 */         R1[p++]=R[j++];     for(p=0,i=low;i<=high;p++,i++)         R[i]=R1[p];/* 归并完成后将结果复制回R[low..high] */ } /* end of Merge */ void Merge_SortDC(int low,int high) {/* 用分治法对R[low..high]进行二路归并排序 */     int mid;     if(low<high)     {/* 区间长度大于1 */         mid=(low+high)/2; /* 分解 */         Merge_SortDC(low,mid); /* 递归地对R[low..mid]排序 */         Merge_SortDC(mid+1,high); /* 递归地对R[mid+1..high]排序 */         Merge(low,mid,high); /* 组合，将两个有序区归并为一个有序区 */     } }/* end of Merge_SortDC */