数据结构课程可能会考到的排序算法：
插入排序 希尔排序 冒泡法 快排 选择排序 堆排序 归并排序
一 插入排序
#include<cstdio> #include<string> #include<cstring> #include<iostream> using namespace std; void print(int a[], int n ,int i) {cout<<i <<":";for(int j= 0; j<8; j++){cout<<a[j] <<" ";}cout<<endl; }void InsertSort(int a[], int n) {for(int i= 1; i<n; i++){if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入int j= i-1; int x = a[i]; //复制为哨兵，即存储待排序元素a[i] = a[i-1]; //先后移一个元素while(x < a[j]){ //查找在有序表的插入位置a[j+1] = a[j];j--; //元素后移 }a[j+1] = x; //插入到正确位置 }print(a,n,i); //打印每趟排序的结果 }}int main() {int a[8] = {3,1,5,7,2,4,9,6};InsertSort(a,8);print(a,8,8);return 0; }
如图所示为插入过程各元素依次寻找位置
二 希尔排序
#include<cstdio> #include<string> #include<cstring> #include<iostream> using namespace std; void print(int a[], int n ,int i) {cout<<i <<":";for(int j= 0; j<8; j++){cout<<a[j] <<" ";}cout<<endl; } /*** 直接插入排序的一般形式** @param int dk 缩小增量，如果是直接插入排序，dk=1**/ void ShellInsertSort(int a[], int n, int dk) {for(int i= dk; i<n; ++i){if(a[i] < a[i-dk]) //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入 {int j = i-dk;int x = a[i]; //复制为哨兵，即存储待排序元素a[i] = a[i-dk]; //首先后移一个元素while(x < a[j]) //查找在有序表的插入位置 {a[j+dk] = a[j];j -= dk; //元素后移 }a[j+dk] = x; //插入到正确位置 }print(a, n,i );}}/*** 先按增量d（n/2,n为要排序数的个数进行希尔排序**/ void shellSort(int a[], int n) {int dk = n/2;while( dk >= 1 ){ShellInsertSort(a, n, dk);dk = dk/2;} } int main() {int a[8] = {3,1,5,7,2,4,9,6};//ShellInsertSort(a,8,1); //直接插入排序shellSort(a,8); //希尔插入排序print(a,8,8); }
希尔排序如图不断缩小比较规模直到相邻比较
三 冒泡法
#include<cstdio> #include<string> #include<cstring> #include<iostream> using namespace std; void bubbleSort(int a[], int n){for(int i =0 ; i< n-1; ++i) {for(int j = 0; j < n-i-1; ++j) {if(a[j] > a[j+1]){int tmp = a[j] ; a[j] = a[j+1] ; a[j+1] = tmp;}}} } void print(int a[], int n ,int i) {cout<<i <<":";for(int j= 0; j<8; j++){cout<<a[j] <<" ";}cout<<endl; } int main() {int a[8] = {3,1,5,7,2,4,9,6};bubbleSort(a,8);print(a,8,8);return 0; }
冒泡法如图所示
四 快速排序
#include<cstdio> #include<string> #include<cstring> #include<iostream> using namespace std; void print(int a[], int n) {for(int j= 0; j<n; j++){cout<<a[j] <<" ";}cout<<endl; }void swap(int *a, int *b) {int tmp = *a;*a = *b;*b = tmp; }int partition(int a[], int low, int high) {int privotKey = a[low]; //基准元素while(low < high){//从表的两端交替地向中间扫描while(low < high && a[high] >= privotKey) --high; //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端swap(&a[low], &a[high]);while(low < high && a[low] <= privotKey ) ++low;swap(&a[low], &a[high]);}print(a,10);return low; }void quickSort(int a[], int low, int high) {if(low < high){int privotLoc = partition(a, low, high); //将表一分为二quickSort(a, low, privotLoc -1); //递归对低子表递归排序quickSort(a, privotLoc + 1, high); //递归对高子表递归排序 } }int main() {int a[10] = {3,1,5,7,2,4,9,6,10,8};cout<<"初始值：";print(a,10);quickSort(a,0,9);cout<<"结果：";print(a,10);return 0; }
快速排序每次比较确定一个位置
五 选择排序
#include<cstdio> #include<string> #include<cstring> #include<iostream> using namespace std; void print(int a[], int n ,int i) {cout<<"第"<<i+1 <<"趟 : ";for(int j= 0; j<8; j++){cout<<a[j] <<" ";}cout<<endl; } /*** 数组的最小值** @return int 数组的键值*/ int SelectMinKey(int a[], int n, int i) {int k = i;for(int j=i+1 ;j< n; ++j) {if(a[k] > a[j]) k = j;}return k; }/*** 选择排序**/ void selectSort(int a[], int n) {int key, tmp;for(int i = 0; i< n; ++i) {key = SelectMinKey(a, n,i); //选择最小的元素if(key != i){tmp = a[i]; a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换 }print(a, n , i);} } int main() {int a[8] = {3,1,5,7,2,4,9,6};cout<<"初始值：";for(int j= 0; j<8; j++){cout<<a[j] <<" ";}cout<<endl<<endl;selectSort(a, 8);print(a,8,8); }
选择排序每次需要扫描一遍剩余序列选出最小（大）的一个放到前面
改进：每趟循环可以确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。
六 堆排序
#include<cstdio> #include<string> #include<cstring> #include<iostream> using namespace std; void print(int a[], int n) {for(int j= 0; j<n; j++){cout<<a[j] <<" ";}cout<<endl; } /*** 已知H[s…m]除了H[s] 外均满足堆的定义* 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选, ** @param H是待调整的堆数组* @param s是待调整的数组元素的位置* @param length是数组的长度**/ void HeapAdjust(int H[],int s, int length) {int tmp = H[s];int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)while (child < length) {if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)++child ;}if(H[s]<H[child]) // 如果较大的子结点大于父结点 {H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点s = child; // 重新设置s ,即待调整的下一个结点的位置child = 2*s+1;} else { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出break;}H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上 }print(H,length); } /*** 初始堆进行调整* 将H[0..length-1]建成堆* 调整完之后第一个元素是序列的最小的元素*/ void BuildingHeap(int H[], int length) { //最后一个有孩子的节点的位置 i= (length -1) / 2for (int i = (length -1) / 2 ; i >= 0; --i)HeapAdjust(H,i,length); } /*** 堆排序算法*/ void HeapSort(int H[],int length) {//初始堆 BuildingHeap(H, length);//从最后一个元素开始对序列进行调整for (int i = length - 1; i > 0; --i){//交换堆顶元素H[0]和堆中最后一个元素int temp = H[i]; H[i] = H[0]; H[0] = temp;//每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整HeapAdjust(H,0,i);} } int main() {int H[10] = {3,1,5,7,2,4,9,6,10,8};cout<<"初始值：";print(H,10);HeapSort(H,10);//selectSort(a, 8);cout<<"结果：";print(H,10);return 0; }
堆排序是一种树形选择排序，是对直接选择排序的有效改进，可以是小顶堆或者大顶堆。
过程：每次建好堆以后取出堆顶吧叶子放到堆顶重新建堆。
七 归并排序
#include<cstdio> #include<string> #include<cstring> #include<iostream> using namespace std; void print(int a[], int n) {for(int j= 0; j<n; j++){cout<<a[j] <<" ";}cout<<endl; }//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n] void Merge(int *r,int *rf, int i, int m, int n) {int j,k;for(j=m+1,k=i; i<=m && j <=n ; ++k){if(r[j] < r[i]) rf[k] = r[j++];else rf[k] = r[i++];}while(i <= m) rf[k++] = r[i++];while(j <= n) rf[k++] = r[j++];print(rf,n+1); }void MergeSort(int *r, int *rf, int lenght) { int len = 1;int *q = r ;int *tmp ;while(len < lenght){int s = len;len = 2 * s ;int i = 0;while(i+ len <lenght){Merge(q, rf, i, i+ s-1, i+ len-1 ); //对等长的两个子表合并i = i+ len;}if(i + s < lenght){Merge(q, rf, i, i+ s -1, lenght -1); //对不等长的两个子表合并 }tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf } }int main() {int a[10] = {3,1,5,7,2,4,9,6,10,8};int b[10];MergeSort(a, b, 10);print(b,10);cout<<"结果：";print(a,10);return 0; }
归并排序将几个有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。
然后再把有序子序列合并为整体有序序列。
*桶排序
#include<stdio.h> #include<stdlib.h> void bucketSort(double* a,int n)//桶排序 {//链表结点描述typedef struct Node{double key;struct Node * next;} Node;//辅助数组元素描述typedef struct{Node * next;} Head;int i,j;Head head[10]= {NULL};Node * p;Node * q;Node * node;for(i=1; i<=n; i++){node=(Node*)malloc(sizeof(Node));node->key=a[i];node->next=NULL;p = q =head[(int)(a[i]*10)].next;if(p == NULL){head[(int)(a[i]*10)].next=node;continue;}while(p){if(node->key < p->key)break;q=p;p=p->next;}if(p == NULL){q->next=node;}else{node->next=p;q->next=node;}}j=1;for(i=0; i<10; i++){p=head[i].next;while(p){a[j++]=p->key;p=p->next;}} }int main() {int i;double a[13]= {0,0.13,0.25,0.18,0.29,0.81,0.52,0.52,0.83,0.52,0.69,0.13,0.16}; //不考虑a[0]bucketSort(a,12);for(i=1; i<=12; i++)printf("%-6.2f",a[i]);printf("\n");return 0;return 0; }
桶排序效率高稳定，流程见图
