梅州建站网络,网站的建设过程,企业手机网站源码下载,网站建设数据库是什么目录 一 基本思想
二 直接插入排序
三 希尔排序 一 基本思想
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中#xff0c;直到所有的记录插入完为 止#xff0c;得到一个新的有序序列 。 实际中我们玩扑克牌时#xff0c;就用了插入排序的思想
二…目录 一 基本思想
二 直接插入排序
三 希尔排序 一 基本思想
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为 止得到一个新的有序序列 。 实际中我们玩扑克牌时就用了插入排序的思想
二 直接插入排序
当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移
直接插入排序的特性总结
1. 元素集合越接近有序直接插入排序算法的时间效率越高
2. 时间复杂度O(N ^ 2)
3. 空间复杂度O(1)它是一种稳定的排序算法
4. 稳定性稳定
#includestdio.h
void InsertSort(int* a, int n)
{int i 0;for (i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;//因为前面end--了 所以这里是a[end1]}
}
int main()
{int arr[] { 1, 3, 2, 5, 4, 7, 9 };InsertSort(arr, sizeof(arr) / sizeof(int));//排升序for (int i 0; i sizeof(arr) / sizeof(int); i){printf(%d , arr[i]);}
} 三 希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个n 组所有距离为gap的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达gap 1时所有记录在统一组内排好序。 void ShellSort(int* a, int n)
{int gap n;while (gap 1){//gap / 2;gap gap / 3 1;//这样可以更快//直接插入排序思想for (int i 0; i n- gap; i){int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}int main()
{int arr[] { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5};//InsertSort(arr, sizeof(arr) / sizeof(int));//排升序InsertSort(arr, sizeof(arr) / sizeof(int));//排升序for (int i 0; i sizeof(arr) / sizeof(int); i){printf(%d , arr[i]);}
} 希尔排序的特性总结
1. 希尔排序是对直接插入排序的优化。
2. 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的 希尔排序的时间复杂度都不固定
4. 稳定性不稳定 本节的重难点是希尔排序, 希尔排序实际上就是直接插入排序的优化, 只要理解了直接插入排序, 希尔排序就不难了.大家可以根据图解和代码进行实操.
继续加油!
