一直接插入排序
直接插入排序是个稳定的排序算法,适用于关键码n较小,在已知关键码基本有序情况(最好的情况,时间复杂度为0(n),只比较元素n-1次,不移动元素),最坏的情况下时间复杂度为0(n^2),比较元素次数为n(n-1)/2,移动元素次数为(n+3)(n -2)/2,空间复杂度为0(1)
下面实现直接插入排序(递增序列)
#include <stdio.h>
#include <stdlib.h>
void insertSort(int *data,int n){
int j, temp;
for(int i = 1;i <n;i++){
// 比较 n-1趟
if(data[i-1] > data[i]){
temp = data[i];
data[i] = data[i -1];
// 移动元素
for(j = i - 2;j >= 0 && data[j] > temp;j--) data[j + 1] = data[j];
data[j + 1] = temp;
}
}
}
int main(int argc ,char *argv[]){
int data[] = {3,2,4,5};
insertSort(data,4);
for(int i = 0;i < 4;i++){
printf("%d ",data[i]);
}
return 0;
}
2 冒泡排序
冒泡排序也是一个稳定的排序,在待排关键码基本有序的情况下,只需要(n-1)次比较,不需要交换元素(O(n),1趟排序),关键码逆序的情况下,需要n(n-1)/2次比较,关键码n(n -1)/2次交换(O(n^2),n-1趟排序)
冒泡排序的实现(递增序列):
#include <stdio.h>
#include <stdlib.h>
void bubbleSort(int *data,int n){
int temp;
int tag = 1; // 是否交换元素
//最多n-1趟
for(int i = 1; i< n && tag;i++){
tag = 0;
for(int j = 0; j < n -i; j++){
if(data[j] > data[j+1]){
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
tag = 1;
}
}
}
}
int main(int argc, char *argv[]){
int data[] = {10,8,11,9};
bubbleSort(data,4);
for(int i= 0 ; i < 4 ;i++){
printf("%d ",data[i]);
}
return 0;
}
总结
直接插入排序和冒泡排序,时间复杂度和空间复杂度相同,但直接插入排序关键码移动次数明显比冒泡排序少,实际应用直接插入排序更加有效,更广.
