排序集锦
各种排序算法，总结一下，一直在遗忘......
【冒泡排序】
就是下面这个鬼啦：
c实现代码（升序）：
#include<stdio.h> void BubbleSort(int *array,int num) { int i,j,temp; for(j=0;j<num;j++) { for(i=1;i<num-j;i++) { if(array[i-1]>array[i]) //倒序就把这里改成<咯 { temp=array[i-1]; array[i-1]=array[i]; array[i]=temp; } } } } int main() { int num; scanf("%d",&num); int array[num]; int i; for(i=0;i<num;i++) { scanf("%d",&array[i]); } BubbleSort(array,num); for(i=0;i<num;i++) { printf("%d ",array[i]); } printf(" "); return 0; }
【插入排序】
按顺序插入
C语言实现：
#include<stdio.h> void insertionsort(int *array,int num) { int i,j; for(i=1;i<num;i++) { int current=array[i]; j=i-1; while(j>=0 && array[j]>current) { array[j+1]=array[j];//后移为current空出位置 j--; } array[j+1]=current;//将current插入空位 } } int main() { int num; scanf("%d",&num); int array[num]; int i; for(i=0;i<num;i++) { scanf("%d",&array[i]); } insertionsort(array,num); for(i=0;i<num;i++) { printf("%d ",array[i]); } printf(" "); return 0; }
【希尔排序】
C语言实现代
#include<stdio.h> void shellsort(int *array,int num) { int i,j,increment,temp; for(increment=num/2;increment>0;increment/=2) { for(i=increment;i<num;i++) { temp=array[i]; for(j=i;i>=increment;j-=increment) { if(temp<array[j-increment]) { array[j]=array[j-increment]; } else { break; } } array[j]=temp; } //这里其实跟普通插入一样咯，除了间隔大点 } //更改步长，直至最后increment=1，即为普通插入排序 } int main() { int num; scanf("%d",&num); int array[num]; int i; for(i=0;i<num;i++) { scanf("%d",&array[i]); } shellsort(array,num); for(i=0;i<num;i++) { printf("%d ",array[i]); } printf(" "); return 0; }
【选择排序】
C语言实现代码：
#include<stdio.h> void selectionsort(int *array,int num) { int i,j,minindex,temp; for(i=0;i<num;i++) //从0开始挑选出i之后最小的数放到i的位置 { minindex=i; for(j=i+1;j<num;j++) { if(array[j]<array[minindex]) { minindex=j; } } temp=array[i]; array[i]=array[minindex]; array[minindex]=temp; } } int main() { int num; scanf("%d",&num); int array[num]; int i; for(i=0;i<num;i++) { scanf("%d",&array[i]); } selectionsort(array,num); for(i=0;i<num;i++) { printf("%d ",array[i]); } printf(" "); return 0; }
【归并排序】
排序过程动图：
C语言实现代码：
#include<stdio.h> void merge(int *array,int left,int mid,int right) { int temp[right-left+1]; int pos=0,lpos=left,rpos=mid+1; int i;
/*分两个阶段考虑：
①左右两端都未遍历完——比较排序
②有一边遍历完但另一边没有——将未遍历完的依次添加到排序数列后面
最后将temp放入array*/
while(lpos<=mid&&rpos<=right)
{
if(array[lpos]<array[rpos])
{
temp[pos++]=array[lpos++];
}
else
{
temp[pos++]=array[rpos++];
}
}
//阶段①↑ while(lpos<=mid) temp[pos++]=array[lpos++]; while(rpos<=mid) temp[pos++]=array[rpos++];
//阶段②↑ for(i=0;i<pos;i++) { array[i+left]=temp[i]; }
} //归并过程 void mergesort(int *array,int left,int right) { int mid=(left+right)/2; if(left<right) //当left=right，返回上层进行merge() { mergesort(array,left,mid); mergesort(array,mid,right); merge(array,left,mid,right); } //递归 } int main() { int num; scanf("%d",&num); int array[num]; int i; for(i=0;i<num;i++) { scanf("%d",&array[i]); } mergesort(array,0,num-1); for(i=0;i<num;i++) { printf("%d ",array[i]); } printf(" "); return 0; }
Properties ∠( ᐛ 」∠)_：
| 最差时间复杂度 |  |
|---|---|
| 最优时间复杂度 |  |
| 平均时间复杂度 | |
| 最差空间复杂度 | |
【快速排序】
Quick Sort是Bubble Sort改进方法。
和归并一样用到分治思想。
图示：
C语言实现代码：
#include<stdio.h> void quicksort(int *array,int from,int to) { if(from>=to) return; int pivot=array[from]; //pivot就是划分数，即开头那个数啦（其实选哪个数做pivot随你啦） int i=from,j,temp; for(j=from+1;j<=to;j++) //遍历pivot之后的数 { if(array[j]<pivot) { i=i+1; //i在计数比pivot小的数的数量 temp=array[i]; array[i]=array[j]; array[j]=temp; } } //通过这个循环将划分区域内数按大小关系分成大于pivot和小于pivot两拨 temp=array[i]; array[i]=array[from]; array[from]=temp; //将i位置与起始位置数值调换，将pivot换到中间值，原i位置是右边那拨最小数 quicksort(array,from,i-1); quicksort(array,i+1,to); //递归，对pivot两边区域继续quicksort } int main() { int num; scanf("%d",&num); int array[num]; int i; for(i=0;i<num;i++) { scanf("%d",&array[i]); } quicksort(array,0,num-1); for(i=0;i<num;i++) { printf("%d ",array[i]); } printf(" "); return 0; }
其他堆排序什么的之后鞋数据结构再说吧QAQ