排序2：直接选择排序、堆排序、直接插入排序、希尔排序
1.选择排序
1. 直接选择排序：
- 思路：每次选择最大或最小数字下标，与数组最后一个元素交换。
- 升级版：每次选最大和最小，分别在头和尾处交换。
- 普通版步骤：
- 头尾标记位：begin、end。
- 遍历中选最大最小
- a
- 普通版代码：
void SelectSort(int* a, int n)
{
int maxi = 0;
for (int end = n - 1; end > 0; end--)
{
maxi = 0;
for(int i = 0; i <= end; i++)
{
if (a[maxi] < a[i])
maxi = i;
}
Swap(&a[maxi], &a[end]);
}
}
- 普通版代码分析：
- 先写内层：每次从0到末尾end，内层做加加，但是每次的end在减1，所以外层控制end。且end做减减。
- 外层控制次数，且控制末尾。因为每次end在减小。所以从end = n-1处到位置1处，这样最后剩下1个元素肯定有序了。
- maxi每次都是要从0开始往后走。
- 升级版代码：
void SelectSortTwo(int* a, int n)
{
int maxi = 0;
int mini = 0;
for (int end = n - 1, begin = 0; begin <= end; end--, begin++)
{
printf("%大的位%d 小的位%d\n", end, begin);
maxi = begin;
mini = begin;
for (int i = begin+1; i <= end; i++)
{
if (a[maxi] < a[i])
maxi = i;
if (a[mini] > a[i])
mini = i;
}
Swap(&a[maxi], &a[end]);
if (mini == end)
mini = maxi;
Swap(&a[mini], &a[begin]);
}
}
- 升级版代码分析：
- 现在多了一个mini，mini放首，所以也多一个begin，因为一轮同时放begin和end。在原始基础代码上加做修改。
- 每一遍去找mini、maxi，所以每一轮起始初始为begin。
- 注意内部的起始位置和终止位置都要发生改变，且每一轮初始为begin+1。
- 犯过错：每次循环外要做两次Swap，如果首尾位置存在最大或最小，先交换的时候要考虑，会不会影响后面的位置，所以要加判断。，此外，我是通过边调试边画图的，F10会直接跳过某个函数。
- 复杂度分析：
O(n^2)：每次都要从头到尾遍历，但是每次减1，所以显然是：n+n-1+n-2+…1 = n ^2 / 2 => O(n^2)。 - 稳定性分析：
显然相同的数字位置会发生改变，是不稳定的。
比如对于【5、5、5、9、1】，最小在最后，1和第一个5交换后，显然第一个5和第二个第三个5的相对位置会发生变化。
2. 堆排序
前面有博客分析过，最好的堆排序时间复杂度为O(N)。做法是：默认堆已经建好【直接利用数组本身】，从最后一个父节点开始到根节点，不断做向下调整。
涉及公式总结：
用父求子：左：left = parent * 2 + 1 右：right = parent * 2 + 2
用子求父：(child - 1) / 2
求最后一个父节点：n个节点最后一个孩子是n-1，求父亲 (n-1-1) /2，所以下面最后一个父节点是：【(n-2)/2】
- 思路：
- 堆排序：从最后一个父节点起：【(n-2)/2】，因为n-1是最后一个孩子，而(child-1)/2是父节点。
- 向下调整：
每次的向下调整都是从爹开始，向下调整。
求儿子位置，因为爹要和儿子做比较，如果小(大)则交换。注意要判断右儿子存在不存在。直到n-1位置。
比较的循环范围是：minchild < n ，循环爹的最小的儿子比：左孩子一定是存在的，然后看右孩子存在不，如果右孩子存在且更小，就替换。
min_child+1 < n：因为C语言数组错误读不会报错。
大于就交换。
巧妙：一旦发现a[parent] 不符合>a[min_child]就停止。但是大于就一直往下。
重要的事情再说三遍：
查右儿子是否存在：使用代码：minchild+1 < n ，因为C语言数组错误读不报错。
查右儿子是否存在：使用代码：minchild+1 < n ，因为C语言数组错误读不报错
查右儿子是否存在：使用代码：minchild+1 < n ，因为C语言数组错误读不报错
- 代码：
void AdjustDown(int* a, int n, int parent)
{
int min_child = 2 * parent + 1;
while (min_child<n)
{
if (min_child + 1 < n && a[min_child + 1] < a[min_child])
min_child++;
if (a[parent] > a[min_child])
{
Swap(&a[parent], &a[min_child]);
parent = min_child;
min_child = parent * 2 + 1;
}
else
break;
}
}
void HeapSort(int* a, int n)
{
int parent = (n-1-1)/2;
for (int i = parent; i >= 0; i--)
{
// 对a、n个数、从点i处做
AdjustDown(a, n, i);
}
}
- 代码分析：
- 堆排序的分析：由于使用复杂度O(N)的建堆做法，步骤是直接从数组上操作。从最后一个父亲节点开始做向下调整。所以i范围：【(n-1-1)/2，0】，做减减。
向下调整分析：向下调整每次都是从父parent到n-1位置，如果局部堆已经符合了大于小于关系，就停止。此外，注意需要判断右儿子是否存在且是否大于min_child，min_child默认是左孩子。
-
复杂度分析：
-
稳定性分析：
堆排序不稳定，比如原本堆：【5,6，7，9,9,9,9,9】。出堆顶5后，最后一个9上去，显然即使向下调整，几个9之间的相对位置已经发生了改变。
2.插入排序
1. 直接插入排序：
- 思路：
默认数组0位置即第一个数字已经有序，然后不断用后面的数字跟前面比较，如果大于的都往后挪动，直到找到小于位置。 - 代码：
写法（一）
void insertSort(int* a, int n)
{
int tmp = 0;
int j = 0;
for (int i = 1; i <= n - 1; i++)
{
tmp = a[i];
for (j = i; a[j-1] > tmp && j >=0 ; j--)
{
a[j] = a[j - 1];
}
if (j < 0)
j = 0;
a[j] = tmp;
}
}
- 代码分析：
- 第一次比a【1】，第二次a【2】，第三次a【3】。。。每次都在变化着一直向前比，且向前最坏到a【0】，必须双重循环。外层是当前要排序的数字，内层循环是控制之前比它大的做移位。移位之前，先保存a[i]为tmp。
- 挪到过程中，防止错误读，给j加限制，不然j会到-1，是不存在的，但是C语言不报错。
- 注意移位到0，如果a【0】仍然大于当前，j已经到了-1，如果j = -1了，先给j变为0，再给a[j]。如果tmp>a[j-1]，说明可以放了。但是小于的时，已经把之前都挪到过去了。当前j位置就是。
- 代码写法（二）
void insertSort(int* a, int n)
{
int tmp = 0;
int j = 0;
for (int i = 0; i <= n - 2; i++)
{
int end = i;
tmp = a[end + 1];
for (j = end; j >= 0; j--)
if (a[j] > tmp)
a[j + 1] = a[j];
else
break;
a[j+1] = tmp;
}
}
- 代码分析：
给【0, end】插值： 从1开始，
因为要插当前tmp，所以先存起来tmp 【0， end】
有序区间是【0~end】，从end开始往前走到0,
注意这样的挪法，j的后一位是可用位置
i ：【0，n-2】，end从0开始，默认a【0】有序了。tmp是end+1位置，每次向前都要到a【0】位。
- 复杂度分析：
按最坏来看，n-1+n-2+n-3+。。。+1 = n^2 / 2。
所以时间复杂度是 o(n^2)。 - 稳定性分析：
显然，遇到等于情况可以让停止，所以直接插入可以实现相同数字排序过程中相对位置不变。插入排序是稳定的。
2. 希尔排序 - 思路：
对每个以gap为间隔的数组，做排序，gap从大到小变化。gap越大，大的数越快地往后走，gap越小，越接近有序，且gap=1时，是插入排序，此时基本有序，速度会很快。gap==1时相当于做直接插入排序。
- 代码：
void shellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i <= n - 1 - gap; i++)
{
int end = i;
int tmp;
int j;
tmp = a[end + gap];
for (j = end; j >= 0; j -= gap)
{
if (a[j] > tmp)
a[j + gap] = a[j];
else
break;
}
a[j + gap] = tmp;
}
}
}
- 代码分析：
从内向外写，先写一趟排序，再套每一趟，最后改变gap
- 做差为gap的数组的直接插入：
j的范围：从end到0，对以end为尾的范围做插入，我们目的是：j判断当前位置是否大于tmp，大于就往后挪动当前位置值，之后j减gap，
到了j位置，需要j位置有值，所以j大于0即可。- 接着，写变化的end，因为需要对每个数字往前插：范围是：【0,n-1-gap】
end变为i，i范围：【0， n-1-gap】 因为tmp记录的是每个位置的后gap个位置的值,所以0位置也需要，因为要拿0的后gap个。最后一个元素是n-1-gap，
因为它是最后一个存在后gap的位置。i做加加，因为要对每个位置找后gap个做插入。- 对gap：gap要从大到小变化，从大值变为1，必须经过1的时刻。
gap的范围： 初始为n，做 gap = gap / 3 + 1;
循环的条件是： gap > 1 ，- 我一开始加了等于while(gap>=1)，后来运行发现死循环，F11调试后发现，一直在gap==1陷进去了。所以发现，gap>1做排序即可。
-
复杂度分析：
gap>1时都是预排序，为了让数据更接近有序，从而提升gap==1时的排序效率。其时间复杂度不好计算，一般认为是：O(n^1.3)。 -
稳定性分析：
在挪动过程中，相同的数值可能会分到不同数组，使得相对位置发生了改变。所以希尔排序不稳定。