直接插入排序算法思想: 插入第i个数据时,前面的i-1个数据已经排好序,平均时间复杂度为O(n^2),如果找的元素和当前要插入的元素大小一致时,则插入该元素的后面,属于稳定的排序算法。 如排序序列为38 49,65,97,76,13,27,49 第一轮:38 49 待排序: 65,97,76,13,27,49 第二轮:38 49 65 待排序:97,76,13,27,49 第三轮:38 49 65 97 待排序:76,13,27,49 第四轮:38 49 65 76 97 待排序:13,27,49 第五轮:13 38 49 65 76 97 待排序:27,49 第六轮:13 27 38 49 65 76 97 待排序:49 第七轮:13 27 38 49 49 65 76 97优化后的直接插入排序算法(折半插入排序) 由于直接插入排序是边比较边移动元素,由于前面的i-1个数据是已经排好序的,因此可通过折半查找先找出要插入的位置,然后统一将元素全部后移,将比较和移动操作分离。折半插入排序是一种稳定的排序算法再优化:希尔排序(缩小增量排序) Donald Shell 从“减少记录个数”和“基本有序”这两个后面对直接插入进行了改进,提出希尔排序算法,通过将待排序记录按下标一定对增量分组(减少记录个数),对每组记录使用直接插入排序(基本有序),当增量减少至1时,整个序列基本有序,再对全部记录进行一次直接插入排序。
void InsertSortList(int data[],int length){
for (int i = 2; i <= length; i++) {
data[0] = data[i];
int j = i-1;
while (data[j] > data[0]) {
data[j+1] = data[j];
j--;
}
data[j+1] = data[0];
}
}
void InsertBinarySort(int data[],int n){
for (int i = 2; i <= n; i++) {
data[0] = data[i];
int low = 1;
int high = i-1;
while (low<=high) {
int mid = (low + high)/2;
if(data[mid] < data[0]){
low = mid + 1;
}else{
high = mid - 1;
}
}
for (int j = i-1; j >= high+1; j--) {
data[j+1] = data[j];
}
data[high+1] = data[0];
}
}
void ShellSort(int data[],int n){
for (int d = n/2 ; d >= 1; d = d/2) {
for (int i = d + 1; i <= n; i++) {
data[0] = data[i];
int j = i - d;
while (j > 0 && data[0] < data[j]) {
data[j+d] = data[j];
j = j-d;
}
data[j+d] = data[0];
}
}
}
转载请注明原文地址:https://blackberry.8miu.com/read-34470.html