常用的排序算法通俗记忆+代码(未测试)
冒泡排序
从小到大排序
最大的元素在第一次大循环之后到达最后一个位置
从大到小
最小的元素在第一次大循环之后到达最后一个位置
大循环从0~n-1
小循环从0~还未确定的位置
/*从小到大*/
int BubbleSort(int arr[],int length){
for(int i=0;i<n;i++){
for(int j=0;j<length-1-i;j++){/*j+1<length-i*/
if(arr[j+1]<arr[j]){
swap(arr[j+1],arr[j])
}
}
}
}
选择排序
从小到大
从0开始找到最小的元素的索引，和第0个元素交换，从1开始找到第二小的元素，和第1个元素交换
从大到小
从0开始找到最大的元素的索引，和第0个元素交换，从1开始找到第二大的元素，和第1个元素交换
/*从小到大*/
int SelectionSort(int arr[],int length){
for(int i=0;i<length;i++){
int min=i;
for(int j=i+1;j<length;j++){/*从未确定序列的第1个开始，找未确定序列的最小值的索引*/
if(arr[j]<arr[min]){
min=j
}
}
if(min!==i){
swap(arr[i],arr[min])
}
}
插入排序
将无序序列的第1个元素依次与有序序列的元素比较
如果符合条件，则停止比较，进行下1个无序序列的第1个元素的比较；
如果不符合，则交换两个相邻的元素
/*从小到大*/
int InsertSort(int arr[],int length){
for(int i=1;i<length;i++){
for(int j=i;j>0;j--){
if(arr[j]<arr[j-1]){
swap(arr[j],arr[j-1])
}
else{
break;
}
}
}
}
希尔排序
增量为(N/2,N/4，N/8.....1)
第一轮（假设有8个元素）gap增量为4
进行比较的元素索引
4---0
5---1
6---2
7---3
第二轮 gap增量为2
进行比较的元素索引
2--0
3--1
4--2--0
5---3--1 6---4---2--0
7---5---3---1
第三轮 gap增量为1
1---0
2---1---0
3---2---1--0
。。。
7---6---5---4---3---2---1--0
看起来需要移动的数据越来越多，但是越到后面数据是越有序的，所以希尔排序比插入排序效率要高一些
int incSort(int arr[],int gap,int start){
for(int i=start;i>0;i-=gap){
if(arr[i]<arr[i-gap]){
swap(arr[i],arr[i-gap])
}
}
}
for(gap=length/2;gap>0;gap/=2){/*增量的循环*/
for(int start=gap;start<length;start++){/*移动开始元素的下标循环*/
incSort( arr;gap;start)/*有增量插入排序*/
}
}
快速排序（分治思路）
int QuickSort(int arr[],int low,int high){
if(low>=high){
return;
}
int base=arr[low];
int i=low;
int j=high;
while(i<j){
while(i<j&&arr[j]>base) j--;
while(i<j&&arr[i]<base) i++;
swap(arr[i],arr[j]);
i++;j--;
}
swap(arr[j],arr[low]);
QuickSort(arr,low,j-1);
QuickSort(arr,j+1,high);
}
归并排序
递归的方式
mergeSort就是一个外部包含函数，真正的merge函数是边比较边merge
void merge(int *list1,int length1,int *list2,int length ){
int i=0,j=0,k=0;
int m;
int temp[MAXSIZE];
while(i<length1&&j<length2){
if(list1[i]<list2[j]){
temp[k++]=list1[i++];
}else{
temp[k++]=list2[j++];
}
}
while(i<length1){
temp[k++]=list1[i++];
}
while(j<length2){
temp[k++]=list2[j++];
}
for(m=0;m<length1+length2,m++){
list1[m]=temp[m];
}
}
void mergeSort(int list[],int length){
if(length>1){
int *list1=list;
int length1=length/2;
int *list2=list+length/2;
int length2=length-length1;
mergeSort(list1,length1);
mergeSort(list2,length2);
merge(list1,length1,list2,length2);
}
}
迭代的方式(假设8个元素)
for(int i=0;i<length;i*=2){
for(left_min=0;left_min<length-i;left_min=rigth_max+1){
left_max=left_min+i-1;/*left_max是右边最后一个（包含）*/
right_min=left_min+i;
rigth_max=rigth_min+i-1;
int next=0;
while(left_min<=left_max&&right_min<=right_max){
if(list[left_min]<list[right_min]){
temp[next++]=list[left_min++]/*left_min=1*/
}else{
temp[next++]=list[rigth_min++]/*rigth_min=8*/
}
}
/*next=5*/
while(left_min<=left_max){
list[--right_mini]=list[left_max--]/*left_max左边最后一个，right_min现在是8*/
}
/*right_min=4,next=5*/
while(next>0){
list[right_min--]=temp[--next]
}
}
}
堆排序
堆只是父子之间有一定的大小关系，只有根元素是确定的最大或最小的数，其他无法确定
- 待排序数组按原有顺序形成一颗完全二叉树
- 从最后一个非叶子节点进行堆构造，最后一个非叶子节点与它的左右子节点（可以左右子节点先比较）进行比较，然后倒数第二个父节点进行堆构造，直到到达根节点
- 将根元素与堆的最后一个元素交换，开始新一轮的堆构造，此时总长度需要减1
/*最大堆 从小到大 伪代码*/
duiSort(int list[],int n){
while(n){
int lastparent=n/2-1;
while(lastparent>=0){
int larger=compare(list[2*lastparent+1],list[2*lastparent+2]);/*返回大的索引*/
swap(list[lastparent],list[larger]);
}
swap(list[n-1],list[0]);
n--;
}
}
