一、插入排序
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的位置放入tmp a[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; }
六、总结
