Initialcommit

//一、希尔排序 和插入排序的过程相似，相对于插入排序而言，比较较远距离的数据，使得数据移动跨过多个元素，进行一次比较可能会消除多个元素的交换 //最好情况是步长序列只有1，且序列几乎有序，时间复杂度为O(n)。 //希尔本人给出的步长序列，最坏情况时间复杂度是 O(n^2) //希尔排序的时间复杂度与步长序列有关 #include <stdio.h> int main() { int arr[] = {1,5, 2, 7, 6, 4, 9, 8}; int i; for (i = 0; i < 8; i++) { printf("%d ", arr[i]); } printf("\n"); int step; //步长； int key; //保护每一组数据排序时的第二个数据； int j; //该排序过程是多组数据同时进行，并不是一组一组的进行； for (step = 8 / 2; step > 0; step /= 2) { for (i = step; i < 8; i++) { key = arr[i]; //保护数据 for (j = i - step; j >= 0 && arr[j] > key; j -= step) { arr[j + step] = arr[j]; } arr[j + step] = key; //将保护的数据放到合适的位置； } } for (i = 0; i < 8; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; } //结果：1 5 2 7 6 4 9 8 // 1 2 4 5 6 7 8 9

//二、插入排序:最简单常用的方法 //类似于我们打扑克牌的时对手里的牌进行排序的过程，选出一个值，将其插入在合适的排序位置。 //适用于数据量不大，对算法的稳定性有要求，且数据局部或者整体有序的情况。 //时间复杂度为O(n*n). //空间复杂度为O(1); 最好的情况下即当数据有序时可以达到O(n)的时间复杂度 #include<stdio.h> int main() { int a[] = {45,32,56,71,12}; int i,j,temp; printf("未排序前：\n"); for(i=0;i<5;i++) { printf("%d ", a[i]); } printf("\n经过直接插入排序后：\n"); for(i=1;i<5;i++) { temp = a[i]; //当前数小于前一位数时 if(a[i] < a[i-1]) { //将子序列重新排列为有序序列 for(j=i-1;temp<a[j];j--) { a[j+1] = a[j]; } a[j+1] = temp; } } for(i=0;i<5;i++) { printf("%d ", a[i]); } } //结果：未排序前： // 45 32 56 71 12 // 经过直接插入排序后： //12 32 45 56 71

//三、归并排序 时间复杂度为O(nlog)，空间复杂度为O(n)，其需要借助额外的存储空间，是高级排序算法中，唯一一个稳定的排序算法，当数据量较大时，要注意考虑内存空间的开销。

//原理：如果有两个已经排序好的数组{1,4,6,8}，{2,7,9,12}； //我们要把这两个数组合并再排序；目标数组应该是{1,2,4,6,7,8,9,12}；

//四、选择排序法（以从小到大排序为例） //算法思想： //A.在未排序序列中找到最小（大）元素，存放到排序序列的起始位置 //B.从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾 //C.以此类推，直到所有元素均排序完毕 #include<stdio.h> int main() { void sort(int a[],int n); int i,a[10];//定义数组营首地址和数组长度 printf("please input the original array:"); for(i=0;i<10;i++) scanf("%d",&a[i]);//输入十个数 sort(a,10);//调用函数sort对这十个数进行排序 for(i=0;i<10;i++) printf("%5d",a[i]);//输出排序后的十个数 printf("\n"); return 0; }

void sort(int a[],int n)//n是指数组长度 { int min,i,j,t; for(i=0;i<n-1;i++)//数组中的前n-1个数（除最后一个数外）都要进行一趟循环 { min=i;//假设此趟循环中的最小值就是当前值i for(j=i+1;j<n;j++)//第i个数要和后面的每个值比较，与i比较的值记作j if(a[min]>a[j])//若后面的数j更小，则 min=j;//记住此时j的下标 t=a[i];a[i]=a[min];a[min]=t;//将a[i]和a[j]交换位置 } }

//五、冒泡排序法（从小到大排序为例） //算法思想： //1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。 //2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后//的元素会是最大的数，然后将该数固定 //3.针对所有的元素重复以上的步骤，除了最后一个。 //4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

#include<stdio.h> int main() { void sort(int a[],int n); int i,a[10];//定义数组营首地址和数组长度 printf("please input the original array:"); for(i=0;i<10;i++) scanf("%d",&a[i]);//输入十个数 sort(a,10);//调用函数sort对这十个数进行排序 for(i=0;i<10;i++) printf("%5d",a[i]);//输出排序后的十个数 printf("\n"); return 0; }

//六、堆排序 //（一）最大堆调整（Heapify）：将堆的末端子节点作调整，//使得子节点永远小于父节点 //（二）创建最大堆（CreateHeap）：将堆中的所有数据重新//排序 //（三）堆排序（HeapSort）：移除位在第一个数据的根节点，//并做最大堆调整的递归运算 时间复杂度及总结 1、堆排序最大的优点就是，在最坏的情况下，时间复杂度仍为 O(n*logn)；

2、堆排序只需要存放一个记录的辅助空间，所以堆排序也称原地排序；

3、堆排序是不稳定的；

//七、快速排序 //先从数列中取出一个数作轴值（基准数）pivot； //根据基准数将数列进行分区，小于基准数的放左边，大于基准数的//放右边； //重复分区操作，直到各区间只有一个数为止。 #include<stdio.h> int fast(int* y,int begin,int end) { int temp=y[begin]; //将结尾位置保存一下,因为之后的运算会改变end值,end会逐渐向前移动 //,而最后递归的时候end还得是数组的尾元素,不能发生变化 int endTemp=end; //设定递归条件,左右不可相等(重合)如果相等那就return if(end>begin) { //循环条件,左右不可相等(重合),如果相等,那就一次排序分组完毕,开始将分好的两组数组再递归进行排序 while(begin<end) { //向左移动 while((begin<end)&&(temp<=y[end])) end--; y[begin]=y[end]; //向右移动 while((begin<end)&&(temp>y[begin])) begin++; y[end]=y[begin]; } //基准元素放到中间左右重合的位置上 y[begin]=temp; //分组递归,前一组数组为首元素到 fast(y,0,begin-1); fast(y,begin+1,endTemp); } return 0; } int main() { int y[]={22,12,1,33,17,5,10,89,88,30,21,11,11}; fast(y,0,(sizeof(y)/sizeof(int))-1); for(int i=0;i<sizeof(y)/sizeof(int);i++) printf("%d ",y[i]); return 0; }

1 5 10 11 11 12 17 21 22 30 33 88 89

在最好情况下，快速排序算法的时间复杂度为O(nlogn) 在最坏情况下，待排序的序列为正序或者逆序，每次划分只得到一个臂上次划分少一个记录的子序列，而且另一个序列还为空。如果递归树画出来，它就是一棵斜树。此时需要执行(n-1)次递归调用，且第i次划分需要经过i-1次关键字的比较才能找到第i个记录，即中轴元素的位置，因此比较次数为：n-1+n-2+n-3+…+1 = n*(n-1)/2 时间复杂度为O(n^2) //八、基数排序(以整形为例)，将整形10进制按每位拆分，然后从低位到高位依次比较各个位。每次比较完进行排序，直到整个数组有序主要分为两个过程： //(1)分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中（比如53，个位为3，则放入3号桶中) //(2)收集，再将放置在0~9号桶中的数据按顺序放到数组中重复(1)(2)过程，从个位到最高位，直到排好序为止(比如32位无符号整形最大数4294967296，最高位10位)

#include <stdio.h> #define NUM 10 //数组元素个数

void counting_sort(int a[],int b[],int c[],int atemp[]); int main() { int i; int j;

int a[10] = {326,54,512,13,9,71,92,61,53,19}; //input array int atemp[10]; int b[10]; //output array int c[10]; //temp all element are not biger than 10

// 个位排序 for (i = 0;i < NUM;i++) atemp[i] = a[i] % 10; counting_sort(atemp,b,c,a); for (i = 0;i < NUM;i++) a[i] = b[i];

// 十位排序 for (i = 0;i < NUM;i++) atemp[i] = a[i] / 10 % 10; counting_sort(atemp,b,c,a); for (i = 0;i < NUM;i++) a[i] = b[i]; //百位排序 for (i = 0;i < NUM;i++) atemp[i] = a[i] / 100 % 10; counting_sort(atemp,b,c,a);

for (i = 0;i < NUM;i++) printf(" %d ",b[i]); printf("\n");

} //基数排序算法，a为待排序数组(一位数，要和atemp区分开)，b为排序好的数组,c为中间数组，atemp为原始数组(包括三位数) void counting_sort(int a[],int b[],int c[],int atemp[]) { int i,j; for (i = 0;i < NUM;i++) c[i] = 0; for (j = 0;j < NUM;j++) c[a[j]] += 1; for (i = 1;i < NUM;i++) c[i] = c[i] + c[i-1]; for (j = 9;j >= 0;j--) { b[c[a[j]] - 1] = atemp[j]; c[a[j]] -= 1; } }

9 13 19 53 54 61 71 92 326 512