排序算法(实践篇)
插入排序
-
直接插入
void insert_sort(int q[],int n) { int i,j; for(i=2;i<=n;i++) { if(q[i]<q[i-1]) //q[i]<q[i-1]说明要将q[i]插入前面的有序表 { q[0]=q[i];//哨兵=q[i]记录下这个要插入的数值，q[i]比q[i-1]小，要把它放前面 for(j=i-1;q[0]<q[j];j--) //只要当前这个待插入数比q[j]小，就继续往前找 q[j+1]=q[j]; //遍历的同时不断地后移数组，为q[i]让出位置 q[j+1]=q[0]; //把q[i]插入到合适的位置 } } } -
折半插入
void insert_sort(int q[],int n) { int l,r,mid; for(int i=2;i<=n;i++) { if(q[i]<q[i-1]) { q[0]=q[i]; l=1,r=i-1; while(l<=r) { mid=(l+r)/2; if(q[mid]>q[0]) r=mid-1; else l=mid+1; } //二分查找到q[i]应该插入的位置 for(int j=i-1;j>=r+1;j--) q[j+1]=q[j]; //从后往前将数组往后移动，直到j遇到那个q[i]预插入的位置 q[j+1]=q[0]; } } }
交换排序
-
冒泡排序
-
从前往后扫描
void bubble_sort(int q[],int n) { for(int i=0;i<n-1;i++) //最多进行n-1趟排序，每次把最小的数冒泡上浮到0,1,2… { bool flag=false; for(int j=0;j<n-i-1;j--) //j<n-i-1是因为q[n-i-1]到q[n-1]是已确定最终位置的元素 { if(q[j+1]>q[j]) { swap(q[j+1],q[j]); flag=true; } } if(!flag) return; //如果flag==false，说明本趟没有发生排序，排序完成 } } -
从后往前扫描
void bubble_sort(int q[],int n) { for(int i=0;i<n-1;i++) //最多进行n-1趟排序，每次把最小的数冒泡上浮到0,1,2… { bool flag=false; for(int j=n-1;j>=i;j--) //j>=i是因为q[0]到q[i]是经确定最终位置的元素 { if(q[j-1]>q[j]) { swap(q[j-1],q[j]); flag=true; } } if(!flag) return; //如果flag==false，说明本趟没有发生排序，排序完成 } } -
PS:从前往后扫描k遍和从后往前扫描k遍的结果是不一样的，不要用从前往后的逻辑写从后往前
-
-
快速排序
-
void quick_sort(int q[],int l,int r) { if(l>=r) return; //step1：选择一个基准x，将数组分成两边，一边的数全小于x，一边的数全大于x int i=l-1,j=r+1,x=q[(l+r)/2]; while(i<j) { do i++;while(q[i]<x); do j--;while(q[j]>x); if(i<j) swap(q[i],q[j]); } //step2：对数组分成的两边子数组，递归地进行第一步的操作 quick_sort(q,l,j),quick_sort(q,j+1,r); }
-
选择排序
-
简单选择排序
//第i趟从L[i~n]选择关键字最小的元素和L[i]交换，每趟排序确定一个最终位置 void SelectSort(int q[],int n) { for(int i=0;i<n-1;i++) { int min=i; for(int j=i+1;j<n;j++) if(q[j]<q[min]) min=j; swap(q[i],q[min]); } } -
堆排序
#include<bits/stdc++.h> using namespace std; const int N=100010; int h[N],size; int ph[N],hp[N]; //ph数组存储：第i个插入的数在h数组中的下标 //hp数组存储：h数组中的某个下标是第几个插入的 //实现的功能是：任意检索、删除第k个插入的数 //h[ph[k]]就是第k个插入的数，ph[k]就是第k个插入的数下标 //至于hp数组是heap_swap()中的辅助数组 void heap_swap(int a,int b) { swap(ph[hp[a]],ph[hp[b]]); swap(hp[a],hp[b]); swap(h[a],h[b]); } void up(int k) { while(u/2&&h[u/2]>h[u]) { heap_swap(u/2,u); u/=2; } } //把下标为k的结点向上调整 void down(int k) { int t=k; if(k*2<=size&&h[k*2]<h[t]) t=k*2; if(k*2+1<=size&&h[k*2+1]<h[t]) t=k*2+1; //让t等于k以及k左右儿子中的最小值 if(k!=t) { heap_swap(k,t); down(t); } //如果k（父节点）不是三个结点中的最小值，则交换，递归往下 } //把下标为k的结点向下调整 void insert(int x) { size++; m++; ph[m]=size,hp[size]=m; h[size]=x; up(x); } //插入一个数 int getmin() { return h[1]; } //返回堆顶元素 void popmin() { heap_swap(1,size); size--; down(1); } //弹出堆顶元素 void popk(int k) { k=ph[k]; heap_swap(k,size); size--; down(k),up(k); } //弹出第k个插入的数
其他排序
-
归并排序
void merge_sort(int q[],int l,int r) { if(l>=r) return; //step1：分别对左右两侧子序列进行递归排序 int mid=(l+r)/2; merge_sort(q,l,mid); merge_sort(q,mid+1,r); //step2：将两个分别有序的子序列合并成一个有序序列 int k=0,i=1,j=mid+1; while(i<=mid&&j<=r) if(q[i]<=q[j]) tmp[k++]=q[i++]; else tmp[k++]=q[j++]; while(i<=mid) tmp[k++]=q[i++]; while(j<=r) tmp[k++]=q[j++]; //step3：将辅助数组里的有序序列写回q[]数组中 for(int i=0,j=0;i<=r;i++,j++) q[i]=tmp[j]; }