插入排序多种实现:arr,i=1,len=arr.length,flag=arr[i]; 第一趟,比较 flag 与 arr[0] 的大小,若 flag > arr[0],另 arr[i++] = flag; 否则, arr[0] 右移(arr[i] = arr[0])后另 arr[0] = flag; i++ 进行下一趟排序。第二趟,flag 与前两个元素进行比较,在合适位置插入。… 依次进行上述插入,直至排序完成。
这里一个需要注意的问题是,插入的时候,如果前 i 个元素都大于 flag,直接在第一位插入。也就说需要在 j = 0 处加一个岗哨。
这里不难分析,两层循环的时间复杂度为 n^2,(平均为 n^2/4),但我们用到的交换空间为 O(1)。
贴代码:
- function insertFlag(arr, pos, flag) {
- for (var j = pos; j > 0; j--) {
- if (flag < arr[j - 1]) {
- arr[j] = arr[j - 1];
- } else {
- arr[j] = flag;
- break;
- }
- } //岗哨 if(j == 0){ arr[0] = flag; } } function insertSort(arr) { var flag, len = arr.length; for (var i = 1; i < len; i++) { flag = arr[i]; console.log(flag); insertFlag(arr, i, flag); } }
我们这里把插入函数独立出来,是为了之后更好的对插入方法进行改进。上述的方法在待排序的数组比较小的时候,效率比较高,但大的时候就有点力不从心。我们这里的插入,其实是在寻找一个 arr[j] <= flag <=arr[j+1] 的位置,并进行插入。那么如何进行改进呢,当然就是 "折半查找" 咯!(虽然时间和空间没有质的改变,但也是一种改进嘛)
- function binary(arr, pos, flag) {
- var mid, low = 0,
- hign = pos - 1;
- while (low <= hign) {
- mid = Math.ceil((low + hign) / 2);
- arr[mid] < flag ? low = mid + 1 : hign = mid - 1;
- }
- return hign + 1;
- }
- function binaryInsert(arr) {
- var flag, index, len = arr.length;
- if (arr[1] < arr[0]) {
- flag = arr[1];
- arr[1] = arr[0];
- arr[0] = flag;
- }
- for (var i = 2; i < len; i++) {
- flag = arr[i];
- console.log(flag);
- index = binary(arr, i, flag);
- for (var j = i; j > index; j--) {
- arr[j] = arr[j - 1];
- }
- arr[index] = flag;
- }
- }
这里我们为了折半查找的方便,先对 arr 的前两个元素进行排序,然后再进行折半查找并插入。不然看出,我们减少了关键字的比较,但是移动的次数并没有改变,所以时间复杂度依然为 n^2. 空间 O(1)。
2 - 路插入排序主要是为了减少移动的次数。而要想真正达到减少移动次数,最方便的是使用表插入排序,与直接插入排序的差别在于改变了 2n 次指针值代替移动记录,比较次数并没有发生变化。时间复杂度依旧是 n^2。
希尔排序也是插入排序的一种。因为我们知道在数组基本有序,而且数组长度较小的时候,直接插入排序的效率很高(n),希尔排序正是利用了这一点,先将整个待排记录序列分割成若干个子序列,分别进行直接插入排序,待整个记录基本有序时,再对整体序列进行一个直接插入排序。
希尔排序的特点是,分段不是简单的逐段分割,而是将相隔一定增量的的记录组成一个子序列。简单理解的话,就当是先按增量数组进行两两交换,最后用一次直接插入排序。
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/04-07/20093617.html