(排序3)希尔排序时间复杂度与直接选择排序

希尔排序时间复杂度与直接选择排序"/>

(排序3)希尔排序时间复杂度与直接选择排序

TIPS

1. 希尔排序分组预排的目的就在于比如说我要对数据进行升序排序，那么就是可以达到让大的数尽快的调到后面
2. 然后接下来随着gap的不断缩小，间隔越来越小，组也就越来越多，最终整个数组的话是越来越接近有序。
3. 最终的话，你必须要保证这个gap为1，就是说最终必须得进行一次直接插入排序。但此时此刻的直接插入排序是建立在当前这个数组已经是接近有序的情况之下，因此他的时间复杂度远远不用O(N^2)，而是O(N)量级

希尔排序的时间复杂度

1. 首先对于这个gap之间蕴含的数量关系必须得搞清楚
   1. 被分成gap组。
   2. 每组的成员下表只要再加上gap就会跳到下一个同组成员（当然也是同一组的）。
   3. 在每组当中，成员与成员之间隔着gap-1个元素。
2. 希尔排序代码：

void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){gap /= 2;for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i += gap){int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}}
}

3. 先先看外面的这个while循环，这个while循环的话大概需要走logN次。
4. 然后接下来去观察这个while循环里面，在最开始的时候，这个gap很大，比如说是n/2，这时候你依据一下之前讲的有关于gap的数量关系，你会发现里面的数量级应该是O(N)。
5. 那么如果分析最后情况的话，在最后的时候，这个gap很小，比如说最后gap变为一，这时候根据之前还是讲过的那个有关于gap的数量关系，你会发现里面的数量级还是O(N)，虽然说直接插入排序，它的时间复杂度是N^2，但是这边的话主要是前面已经经过了大量的预排序，所以说整个数组已经变得非常非常有序了，所以说他的量级就O(N)。
6. 所以说希尔排序的话，它的时间复杂度总体上跟堆排序差不多，也是NlogN这个量级，实际上应该是比这个量级还要大一点的.
7. 所以说这个只需要记个结论就可以，希尔排序的时间复杂度是N的1.3次方。

选择排序

1. 首先先去定义一下左右边界lefti, righti，然后先去遍历一下从左边界到右边界，然后在这个遍历的过程当中去记录一下最大的值的下标maxi与最小的值的下标mini。然遍历完之后得到这两个下标之后，去把它们分别与左右边界进行交换。然后再把左右边界分别缩短一个，再去进行遍历
2. left, right, maxi, mini都是下标

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void SelectSort(int* arr, int n)
{int lefti = 0;int righti = n - 1;while (lefti < righti){int mini = lefti;int maxi = lefti;for (int i = lefti; i <= righti; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}Swap(arr + lefti, arr + mini);Swap(arr + righti, arr + maxi);lefti++;righti--;}
}

4. 然后再去扪心自问一下，仅仅就上面的这些代码正确吗？实际上这边有个特别大的漏洞，比如说当你把lefti与mini运行交换了之后，万一此时此刻我的maxi就是lefti，那么这样你事先交换完了，相当于就是把我的这个maxi所指向的真实的最大值给换走了，因此需要去特判一下，如果说maxi与lefti相等，那么我就知道maxi已经被调包掉了，并且最大值的下标此时此刻已经是mini了，于是就maxi=mini

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void SelectSort(int* arr, int n)
{int lefti = 0;int righti = n - 1;while (lefti < righti){int mini = lefti;int maxi = lefti;for (int i = lefti; i <= righti; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}Swap(arr + lefti, arr + mini);if (maxi == lefti){maxi = mini;}Swap(arr + righti, arr + maxi);lefti++;righti--;}
}

选择排序时间复杂度

1. 时间复杂度O(N^2)。
2. 并且不管最好与最坏情况，都是N^2。就是说需要排序的一个序列，不管怎么样对这个选择排序的性能是没有任何影响，管你无序还是接近有序呢。
3. 为什么是属于N的平方级别？你就去想想整个的遍历过程，一开始需要去遍历n个，然后n-2个，然后n-4个，然后以此不断递减，是一个标标准准的等差数列，所以到时候总和加起来肯定是O(N^2)