1 排序算法的比较
1）验证：无论数据的初始状态是什么，排序算法一定能成功吗？
2）运行时间：基本操作的次数（包括比较和交换，或者是读写数组的次数）。
3）额外的内存使用。
4）数据类型。
2 选择排序
步骤：
1）找到未排序数组中最小的元素。
2）将该元素与未排序的元素的最小位置元素进行交换。
特点：
1）运行时间和输入无关。
2）数据移动是最少的。（用了N次交换）
3 插入排序
步骤：
1）选择未排序的第一张A与已排序倒序的进行比较。
2）如果A比该元素小，则将A于该元素交换位置，接着再比较下一个。
3）如果A不小于该元素，则停止此次比较。
特点：对于随机排列的长度为N且主键不重复的数组。
1） 平均情况下插入排序需要~N2/4次比较，以及~N2/4次交换。
2）最坏情况下需要~N2/2次比较，以及~N2/2次交换。
2）最好情况下需要N-1次比较，以及0次交换。
几种典型的部分有序的数组：
1）数组中每个元素距离它的最终位置都不远。
2）一个有序的大数组接一个小数组。
3）数组中只有几个元素的位置不正确。
插入排序需要的交换次数操作和数组中倒置的数量相同，需要的比较次数大于等于倒置的数量，小于等于倒置数量加上数组的大小再减一。
4 希尔排序
希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。 这样的数组被称为 h 有序数组。
如何选择递增序列呢(h = 3*h + 1)？
使用递增序列 1, 4, 13, 40, 121, 364…的希尔排序所需的比较次数不会超出 N 的若干倍 乘以递增序列的长度。
附录一个c++实现的以上排序代码
#include <iostream>
using namespace std;
typedef void (*Fp)(int* a, int count);
void Myswap(int &a, int &b){
int tmp = a;
a = b;
b = tmp;
}
//选择排序
void Selection_sort(int *a, int count);
//插入排序
void Insert_sort(int *a, int count);
//希尔排序
void Shell_sort(int *a, int count);
int main()
{
int count = 10;
int a[] = { 3, 32, 55, 216, 7, 23, 233, 1, 13, 4 };
cout << "排序前：" << endl;
for (int i = 0; i < 10; i++){
cout << a[i] << " ";
}
cout << endl;
//Fp fp = Selection_sort;
//Fp fp = Insert_sort;
Fp fp = Shell_sort;
fp(a, count);
cout << "排序后：" << endl;
for (int i = 0; i < 10; i++){
cout << a[i] << " ";
}
cout << endl;
return 0;
}
void Selection_sort(int *a, int count){
int min = 0;
for (int i = 0; i < count; i++){
min = i;
for (int j = i + 1; j < count; j++){
if (a[min] > a[j]){
min = j;
}
}
Myswap(a[i], a[min]);
}
}
void Insert_sort(int *a, int count){
for (int i = 1; i < count; i++){
for (int j = i; j>0 && a[j] < a[j - 1]; j--){
Myswap(a[j], a[j - 1]);
}
}
}
void Shell_sort(int *a, int count){
int h = 1;
while (h < count / 3)
h = 3 * h + 1;
while (h >= 1){
for (int i = h; i < count; i++){
//将a[i]插入到a[i-h],a[i-2*h],a[i-3*h]...之中
for (int j = i; j >= h&&a[j] < a[j - h]; j -= h){
Myswap(a[j],a[j - h]);
}
}
h = h / 3;
}
}
