一 摘要
排序算法是很重要的在计算机科学中。
二 各种排序算法的实现
这里，性能的分析最后补上，因为自己的数学实在差劲。 尤其注意一下需排序数组的下标从0开始还是从1开始，这两者在实现上有很大的不同。 本文所有的排序都是从0开始的，尽管自己因为这个标准吃尽了苦头
2.1合并排序
code 这里的合并排序只是简单的使用一个数组，没有考虑两个数组的情况，其实是一样的。 请记住，在执行完两个子数组的其中任何一个接下来执行的操作，这才是重点。参数 为你要排序的数组、起始位、中间位、结尾。
2.2交换排序
bubble sort
所谓的冒泡排序大家都听说过，这里直接上代码，不过你要注意那个标志符的作用。我 还是在老地方犯错：先是一个while、接着for，之间填一个sorted=1;这样效率上会有 提升。
/*我的困难局限于标志变量的位置*/
void bubblesort(int a[],int n){
int i,j,temp,sorted;
i = sorted = 0;
while( (i < n - 1) && (!sorted)){
sorted = 1;
for(j = n - 1; j > i; j--){
if(a[j] < a[j-1]){
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
sorted = 0;
}
}
}
}
2.3 插入排序
插入排序分为直接插入排序和希尔排序
插入排序
将一个记录插入到已排序良好的有序表中，从而得到一个记录数增加1的新表，直到整 个表有序为止。
要点：
设立哨兵，作为临时存储和判断数组边界之用。 最难的是确定插入的位置，在思维上的模糊感还是特别强。
version 1:
void insert_sort(int a[],int n){
int i,t;
int tmp;
for(i = 1; i < n; i++){ // 只需注意后一项比前一项大的即可
if(a[i] < a[i-1]){
t = i - 1; // 先前移一个元素？这里快想透了
tmp = a[i];
a[i] = a[i-1];
while(tmp < a[t]){ //寻找在有序表插入的位置
a[t+1] = a[t];
t--;
}
a[t+1] = tmp; //将哨兵元素放入其中
}
}
}
我自己写的时候的模糊点：
1. 首先前移一位；
2. 寻找在有序表的位置及移动的方法及将哨兵放入排序后的空缺位置
下面是严蔚敏版数据结构的代码
void insert(int a[],int n){
int i,j;
int tmp;//我没用哨兵，使用的是临时变量
for (i = 1; i < n ;++i){ //..
if(a[i] < a[i-1]){ //说明需要插入有序表
tmp = a[i];
a[i] = a[i-1];
for(j = i - 1 ; a[j] > tmp; --j){ // 移动,
//这里我把比较符号
//搞反了。
a[j+1] = a[j];
}
a[j + 1] = tmp;
}
}
}
效率: O(n^2).
折半插入排序
利用插入排序的基本操作是在一个有序表中进行查找和插入。所以，我们的查找使用折 半.
shell 排序
先将整个待排序的记录序列分割成若干子序列分别进行直接插入排序。
1 确定一个递增序列t1,t2,….tk,最后tk=1；
2 按递增序列个数k，对序列进行k趟排序
这里我们需要处理的序列：增量序列d={n/2,n/4,n/8…1}n为要排序的个数。
void shell_insert(int a[],int n,int dk){
int i;
for(i = dk; i < n; i++){
if(a[i] < a[i-dk]){ //思路上是有些怪诞
int j = i - dk;
int x = a[i];
a[i] = a[i-dk];
while(x < a[j]){
a[j+dk] = a[j];
j -= dk;
}
a[j+dk] = x; //插入排序的最后一步要将空
} //缺的值填补上
}
}
void shell_sort(int a[],int n){
int dk = n/2;
while(dk >= 1){
shell_insert(a,n,dk);
dk /=2;
}
}
影响shell排序的一个重要因素就是dk的选取，最好的效率是nlogn目前。
2.4 选择排序
简单选择排序
基本思想：就是在要排序的一组数中，选出最小（或者最大的）的一个数与第一个数字 交换，以此类推，直到最后一个元素和倒数第二个元素比较位置。注意，是两个元素相 互交互。
比如有以下几个乱序数字：
3 1 5 7 2 4 9 6 8
第一趟排序为1 3 5 7 2 4 9 6 8
第二趟排序为1 2 5 7 3 4 9 6 8
/*
* 之所以传递给一个i，主要也是为了降低
* 复杂度
*/
int select_min_key(int a[],int n,int i){
int k = i;
int j;
for(j = i + 1; j < n; j++){
if (a[k] > a[j]) k = j;
}
return k;
}
void select_sort(int a[], int n){
int key,tmp;
int i;
for(i = 0; i < n; i++ ){
key = select_min_key(a,n,i);
if(key != i){
tmp = a[i];
a[i] = a[key];
a[key] = tmp;
}
}
}
其实我的本意是将两个函数合并在一起的，没有成功呢！这样的思路很熟悉，但是自己 写不出来。
简单选择排序的改进：
在每次的比较中确定最大值和最小值，这样只需要[n/2]次选择即可。
[折半插入排序没有成功]
堆排序
首先是堆的定义：n个元素的序列{k1,k2,…kn}当且仅当满足下列关系时，称之为堆。
Ki <= K2i
Ki <= K2i-1.
而且是一棵完全二叉树，或者说反过来也对.非终端节点的值不大于(或者不小于)左右子节点，所以根节点是最大的元素，这像完全二叉树。所谓的堆排序就是找出其中一个的最值，在其余n-1个数 列中重建堆。如此反复，便能得到一个有序序列，这个过程称之为堆排序。
为此，实现堆排序需要两个解决两个问题：(1)如何构建一个堆(2)如何输出一个堆顶元 素后，调整剩余元素为一个新的堆。
性质在一个模拟堆的数组中，下标为(floor(A[n/2])..n)(其中的括号是向下取整)全都是叶子。
#include<stdio.h>
#include "test_data.h"
int A[10] = {3,1,2,5,9,6,7,4};
/*
* start: 相当于root,start对于数组的观点来说直观
* 从srart到end选取最大的数
* root: 相对于tree来说直观
* 为了方便数组下标从0开始，end应该为个数减1
* 尤其注意这点
*/
void maxheap_down(int a[],int start,int end){
int current = start;
int left = start * 2 + 1;
int tmp = a[current]; /*从根节点、左右子孩子中选择一个最大的*/
for(; left < end; current = left, left = 2 * current + 1){
if(left < end && a[left] < a[left + 1])
left++; //右孩子大
if(a[left] <= tmp)
break; //这一句包含了两种情况
else{ // 调整tmp与大的孩子的值
a[current] = a[left];
a[left] = tmp;
}
}
}
void heap_sort(int a[],int n){
int i,temp;
for(i = n / 2 - 1;i >= 0; i--){
maxheap_down(a,i,n-1);//看你从主函数调用时传递的参数
}
printf("MAX is %d\n",a[0]);
/*从最后一个元素开始，不断缩小范围直至最后一个元素*/
for(i = n - 1;i >= 0; i--){
temp = a[i];
a[i] = a[0];
a[0] = temp;
/*从堆头开始往下再次调整*/
maxheap_down(a,0,i-1);
}
堆排序的时间复杂度和稳定性：
因为有N的数列需要遍历，所以遍历一趟的时间复杂度为O(N).
堆排序采用的是二叉堆进行排序的，二叉堆就是一棵完全二叉树，它需要遍历的次数就 是二叉树的深度。则完全二叉树的深度至少是lg(n+1),最多为lg(2n),二者结合的时间复杂度为O(N*lgN).