整理一些排序算法供自己温习参考。
1 选择排序
选择排序的思路是
1.找到数组中最小的元素，将其与数组第一个元素交换
2.剩下的数据中找最小的元素，将其与数组第二个元素交换
3.重复上面的动作，直到遍历整个数组
特点
1.选择排序需要大约N^2/2次比较和N次交换
2.每个数据都会交换一次，所以总共N次交换，每个数据都会和N-i-1个数进行比较
3.不会因为初始数据状态而改变运行时长
void selectionSort(int* a, int len) {
for(int i = 0; i < len; i++) {
int min = i;//最小元素索引
//找到a[i+1……N]中最小值索引
for(int j = i + 1; j < len; j++) {
if(a[j] < a[min]) {
min = j; //记录a[i+1……N]最小值索引
}
}
//将a[i]与a[i+1……N]中最小数据交换
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}2 插入排序
插入排序的思路是
1.将需要排序的当前元素插入到已经排序好的序列中，所有元素在插入之前都需要向右移动一位。
特点：
对部分有序数据排列十分高效
void insertSort(int* numbers, int len) {
for(int i = 1; i < len; i++) {
//从当前索引i开始往前循环比较，因为第i个元素之前的数据为有序数据
//将当前索引元素i插入到有序数据正确的位置
for(int j = i; j > 0 && (numbers[j] < numbers[j-1]); j--) {
int temp = numbers[j];
numbers[j] = numbers[j-1];
numbers[j-1] = temp;
}
}
}对于随机排序的无重复数组，插入排序和选择排序的运行时间是平方级别的，两者之比是一个很小的常数。
3 希尔排序
希尔排序是为了加快速度简单地改进了插入排序，交换不相邻的元素对数组的局部进行排序，最最终用插入排序将局部有序的数组排序。
排序思想：使数组中任意间隔为h的元素都是有序的。细化为h有序数组。
只需要将插入排序的代码中将移动元素的距离由1改为h即可。
void shellSort(int* numbers, int len){
int h = 1;
while(h < len/3) h = h*3 + 1;
while(h >= 1) {
for(int i = h; i < len; i++) {
//将numbers[j]插入到number[j-h],number[j-2*h]……中
for(int j = i; j >= h && (numbers[j] < numbers[j-h]); j-=h) {
int temp = numbers[j];
numbers[j] = numbers[j-h];
numbers[j-h] = temp;
}
}
h = h/3;
}
}