【Day12 数据结构学习-5】

一 插入排序

1.1 直接插入排序

思想：依次将后面一个元素和前面所有的元素作比较，选择合适的位置插入。

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
void InsertSort(int *a,int length)
{int i,j ,tmp;for(i = 1; i < length;i++){tmp = a[i];for(j = i -1;j >= 0;j--){if(tmp < a[j]){a[j + 1] = a[j];}else{break;}}//找到合适的位置后，在j+1的位置放入tmpa[j + 1] = tmp;}
}
int main(int argc, char const *argv[])
{int i;//int array[10] = {9,4,3,2,1,5,6,8,7,0};int array[10000] = {0};srand(time(NULL));for(i = 0 ; i < 10000;i++){array[i] = rand() % 1000;}InsertSort(array,sizeof(array)/sizeof(array[0]));for(i = 0 ;i < sizeof(array)/sizeof(array[0]);i++){printf("%d ",array[i]);}putchar(10);return 0;
}

1.2 希尔排序

思想：定义一个增量h = length /2,以增量h为间隔进行插入排序，然后将增量h/2再次进行直接插入排序，最后进行增量为1的直接插入排序，此时因该基本有序。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void ShellSort(int *a,int length)
{int i,j,h,tmp;//多个组同时进行直接插入排序for(h = length /2;h > 0;h /= 2){for(i = h; i < length;i++){tmp = a[i];for(j = i - h;j >=0;j-=h){if(tmp < a[j]){a[j + h] = a[j];}else{break;}}a[j + h] = tmp;}}
}
int main(int argc, char const *argv[])
{int i;//int array[10] = {9,4,3,2,1,5,6,8,7,0};int array[10000] = {0};srand(time(NULL));for(i = 0 ; i < 10000;i++){array[i] = rand() % 1000;}ShellSort(array,sizeof(array)/sizeof(array[0]));for(i = 0 ;i < sizeof(array)/sizeof(array[0]);i++){printf("%d ",array[i]);}putchar(10);return 0;
}

二 交换排序

2.1 冒泡排序

2.2 快速排序

思想：通过一趟排序将待排序的序列分割成两个独立的部分，其中一部分记录的数字都比关键字小，另一部分都比关键字大，然后再对这两个部分继续进行排序，以达到整体有序的目的。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void QuickSort(int *a,int start,int end)
{//递归结束的条件：只有一个元素if(start > end){return;}int x = start;int y = end;int base = a[start];while(x < y){while(a[y] > base && x < y){y--;}if(x < y){a[x++] = a[y];}while(a[x] < base && x < y){x++;}if(x < y){a[y--] = a[x]; }}a[x] = base;QuickSort(a,start, x - 1);QuickSort(a,x + 1,end);
}
int main(int argc, char const *argv[])
{int i;//int array[10] = {9,4,3,2,1,5,6,8,7,0};int array[10000] = {0};srand(time(NULL));for(i = 0 ; i < 10000;i++){array[i] = rand() % 1000;}QuickSort(array,0,sizeof(array)/sizeof(array[0])-1);for(i = 0 ;i < sizeof(array)/sizeof(array[0]);i++){printf("%d ",array[i]);}putchar(10);return 0;
}

三 选择排序

3.1 简单选择排序

思想：就是通过n-i关键词的比较，从n-i-1中选出关键词最小的记录，并和第i个记录交换之。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void SelectSort(int *a,int length)
{int i,j,tmp,index;for(i = 0; i < length;i++){tmp = a[i];index = i;for(j = i + 1;j < length;j++){if(a[j] < tmp){tmp = a[j];index = j;}}if(index != i){a[index] = a[i];a[i] = tmp;}}
}
int main(int argc, char const *argv[])
{int i;//int array[10] = {9,4,3,2,1,5,6,8,7,0};int array[10000] = {0};srand(time(NULL));for(i = 0 ; i < 10000;i++){array[i] = rand() % 1000;}SelectSort(array,sizeof(array)/sizeof(array[0]));for(i = 0 ;i < sizeof(array)/sizeof(array[0]);i++){printf("%d ",array[i]);}putchar(10);return 0;
}

3.2 堆排序

思想：将待排序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点，然后将其和某位元素进行交换，然后将除了最后一个元素外的所有元素重新构造成一个堆，这样就会得到n个元素的次大值，如此反复执行，就可以得到一个有序的序列。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>void AdjustHeapSort(int *a,int root,int last)
{int child,tmp = a[root];for(;2*root + 1 <= last;root = child){child = 2*root + 1;if(child + 1 <= last && a[child] < a[child + 1]){child++;}if(a[child] > a[root]){a[root] = a[child];a[child] = tmp;}}
}void Swap(int *a,int *b)
{int tmp = *a;*a = *b;*b = tmp;
}void HeapSort(int *a,int length)
{//构建大顶堆,i为数组下标int i;for(i = length /2 -1; i >= 0;i--){AdjustHeapSort(a,i,length -1);}for(i = length -1; i > 0;i--){Swap(&a[0],&a[i]);AdjustHeapSort(a,0,i - 1);}
}
int main(int argc, char const *argv[])
{int i;//int array[10] = {9,4,3,2,1,5,6,8,7,0};int array[10000] = {0};srand(time(NULL));for(i = 0 ; i < 10000;i++){array[i] = rand() % 1000;}HeapSort(array,sizeof(array)/sizeof(array[0]));for(i = 0 ;i < sizeof(array)/sizeof(array[0]);i++){printf("%d ",array[i]);}putchar(10);return 0;
}

四 归并排序

思想：先将长度为m的序列进行拆分，拆成单独的子序列，然后再两两进行归并，如此重复，最后得到一个有序序列，这种排序称为2路归并排序。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void Merge(int *a,int start,int mid,int end)
{int Left_len = mid - start +1;int Right_len = end - mid;//分为两个部分，然后将两个部分不断进行合并，最后剩下最大的两个部分int *L = (int *)malloc(sizeof(int)* Left_len);int *R = (int *)malloc(sizeof(int)* Right_len);int i,k,j;for(i = 0,k = start;i < Left_len;i++,k++){L[i] = a[k];}for(j = 0;j < Right_len;j++,k++){R[j] = a[k];}for(i = 0,j = 0,k = start; i < Left_len && j < Right_len;k++){if(L[i] < R[j]){a[k] = L[i++];}else{a[k] =R[j++];}}if(j < Right_len){for(;j < Right_len;j++,k++){a[k] = R[j];}}if(i < Left_len){for(;i < Left_len;i++,k++){a[k] = L[i];}}free(L);free(R);L = NULL;R = NULL;
}
void MergeSort(int *a,int start,int end)
{//拆分如果开始位置和结束位置重合，就结束if(start >= end){return;}//找出中间位置int mid = (start + end) / 2;MergeSort(a,start,mid);MergeSort(a,mid + 1,end);//合并Merge(a,start,mid,end);
}
int main(int argc, char const *argv[])
{int i;int array[10] = {9,4,3,2,1,5,6,8,7,0};/*int array[10000] = {0};srand(time(NULL));for(i = 0 ; i < 10000;i++){array[i] = rand() % 1000;}*/MergeSort(array,0,sizeof(array)/sizeof(array[0]) - 1);for(i = 0 ;i < sizeof(array)/sizeof(array[0]);i++){printf("%d ",array[i]);}putchar(10);return 0;
}

五 基数排序（桶排序）

思想：从低位开始将待排序的数按照这一位的值放到相应的编号为0-9的桶种，等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中，一直排到最高位位置，数组排序完成

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void RadixSort(int *a,int length)
{int i,max =a[0],base = 1;for(i = 1; i < length;i++){if(a[i] > max){max = a[i];}}int *t = (int *)malloc(sizeof(int)*length);while(max / base > 0){int bucket[10] = {0};for(i = 0 ; i < length;i++){bucket[a[i] / base % 10]++;}for(i = 1; i < 10;i++){bucket[i] += bucket[i -1];}for(i = length -1; i >=0;i--){t[bucket[a[i] /base % 10] -1] = a[i];//同一个位置出现多个数字的时候，要往前挪bucket[a[i]/base %10]--;}for(i = 0 ; i < length;i++){a[i] = t[i];}base = base *10;}
}
int main(int argc, char const *argv[])
{    int i;//int array[10] = {9,4,3,2,1,5,6,8,7,0};int array[10000] = {0};srand(time(NULL));for(i = 0 ; i < 10000;i++){array[i] = rand() % 1000;}RadixSort(array,sizeof(array)/sizeof(array[0]));for(i = 0 ;i < sizeof(array)/sizeof(array[0]);i++){printf("%d ",array[i]);}putchar(10);return 0;
}

六 总结