赞
踩
从左往右比较依次选出下一个数插入到前面有序区间合适的位置。
[图片为转载博主一像素]
void InsertSort(int arr[], int size) { for (int i = 1; i < size; i++) { int key = arr[i]; int end = i - 1; while (end >= 0 && key < arr[end]) { arr[end + 1] = arr[end]; end--; } arr[end + 1] = key; } }
挪动的次数数组的长度
最优情况:待排序序列接近有序,要移动的关键字只有常数此,它的时间复杂度O(n)。
最坏情况:待排序序列基本无序,时间复杂度为O(NN)。
只开辟了一个空间所以为O(1)。
元素集合越接近有序,直接插入排序算法的时间效率就越高。
所以考虑到这点可以使用折半查找算法对其进行优化,该优化只减少了在有序区域比较的次数,并没有减少元素移动数。
void InsertSort(int arr[], int size) { for (int i = 1; i < size; ++i) { int key = arr[i]; int end = i - 1; int left = 0; //二分查找先找到位置 int right = i - 1; while (left <= right) { int mid = left + ((right - left)>>1); if (arr[mid]>key) right = mid - 1; else left = mid + 1; } while (end >=left) { arr[end + 1] = arr[end]; end--; } arr[end + 1] = key; } }
又称缩小增量排序,也是对直接插入排序的优化
把小的数据尽可能往前排,把大的数据尽可能往后排,这样在进行最终插入排序时,后面的数就不会很小,这样挪动的次数就减小了。
[图片为转载博主一像素]
代码实现:取一个小于n的gap(步长),通过把所有距离为gap或者gap的倍数的数据放在一个组里,继续上面的操作,gap越小时,预排序完毕接近有序,当gap等于1时,预排序就相等于直接插入排序。
void ShellSort(int arr[], int size) { int gap = size; while (gap > 1) { gap = gap / 3 + 1;//加1是因为最后gap变为1或者2时,除3结果为1. for (int i = gap; i < size; i += gap) { int key = arr[i]; int end = i - gap; while (end >= 0 && arr[end]>key) { arr[end + gap] = arr[end]; end -= gap; } arr[end + gap] = key; } } }
希尔排序的时间复杂度与gap增量有关,平均时间复杂O(n*log(n)),大概是O(n^1.3),
顺序情况下,相比较选择直接插入排序更好一点,它的时间复杂度为O(n)。
逆序情况下,相比较选择希尔排序更好一点。
一次插入排序是不会改变相同元素的位置,但是多次插入排序,就会改变不同组里的相同元素的相对位置,因此希尔排序时不稳定。
当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就
会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
希尔排序使较大的数据往后移动,接近有序,所以效率比直接插入排序要高。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。