堆排序，快速排序

目录

1.堆排序

2.快速排序

1.hoare版本

2.挖坑法

3.前后指针法

注意点

---

1.堆排序

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
void adjustdown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);}else{break;}parent = child;child = parent * 2 + 1;}
}
void heapsort(int* a, int n)
{for (int i = (n - 1 -1) / 2; i >= 0; i--){adjustdown(a, n, i);}for (int i = n-1; i > 0; i--){Swap(&a[0], &a[i]);adjustdown(a, i, 0);}
}void printarr(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}
void heaptest()
{int arr[] = { 4,7,1,9,3,6,5,8,3,2,0 };printarr(arr, sizeof(arr)/sizeof(int));heapsort(arr, sizeof(arr)/sizeof(int));printarr(arr, sizeof(arr)/sizeof(int));
}

        我们先用向下调整算法建堆。

        使用向下调整算法建堆的前提是，该节点的子树都是堆。那么我们从最后一个节点的父节点开始向下调整算法，这样因为两个子树都是叶子节点，因此满足条件。从后往前，一直遍历到父节点为根节点，那么就建好堆了。

        然后只需要不断将第一个和最后一个节点的值交换，把最大值放到末尾，然后不断从根节点向下建堆，即可每次都挑选出最大值，我们依次把他们放到末尾即可。 

2.快速排序

主逻辑，递归

1.hoare版本

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void printarr(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}int partsort(int* a, int left, int right)
{int keyi = left;while (left < right){while (left < right &&a[left] <= a[keyi]){left++;}while (left < right && a[right] >= a[keyi]){right--;}Swap(&a[left], &a[right]);//如果是因为left==right结束，交换值也并不影响结果}Swap(&a[keyi], &a[left]);return left;
}void quicksort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = partsort(a, begin, end);quicksort(a, begin, keyi-1);quicksort(a, keyi + 1, end);
}void quicktest()
{int arr[] = { 4,7,1,9,3,6,5,8,3,2,0 };printarr(arr, sizeof(arr) / sizeof(int));quicksort(arr,0, sizeof(arr) / sizeof(int)-1);printarr(arr, sizeof(arr) / sizeof(int));
}

我们以左边第一个下标为keyi，因此先从右边开始找

1.先从右往左找到比a【keyi】小的值

2.再从左往右找到比a【keyi】大的值

交换这两个值。

3.不断重复以上过程直到相遇left == right

4.交换a【keyi】和a【left】

注意点

        1.我们在移动下标时，判断条件是a[left] <= a[keyi]left++

                                                        a[right] >= a[keyi] right--

        这是为了防止遇到与a【keyi】相等的值的时候，陷入死循环

        2.我们在寻找下标的小循环中也加入left<right的判断是因为防止极端情况。

        如果不判断就会越界，而且如果是因为left==right结束，交换值也并不影响结果

        同时因为这个极端情况原因，我们遍历是从最左边keyi处开始遍历，不然会忽略掉这种情况。也是注意点1中判断条件需要加=的原因

 

 3.我们再来谈谈为什么从一边开始调整要从另一边开始找起

以上面的情况为例子，

因为这样可以保证他们相遇时候所处在的值一定比a【keyi】小

情况1、left不动，right先移动与left相遇，此时a【keyi】还在原位

情况2.  right移动后找到小值，left移动后与right相遇，此时该位置的值比a【keyi】小

情况3，left与right先各自移动并且交换一次，然后right再移动和left相遇，此时因为已经交换过，a【left】处储存的值小于a【keyi】因此也符合

综上

2.挖坑法

 

int partsort(int* a, int left, int right)
{int key = a[left];while (left < right){while (left < right && a[right] >= key){right--;}a[left] = a[right];while (left < right && a[left] <= key){left++;}a[right] = a[left];}a[left] = key;return left;}

 

 

 

 

 

把a【keyi】的位置先挖走，记录这个key值。

1.从右边往左找小，把这个值填入坑中，同时这个位置形成一个新的坑

2.从左边往右找大 把这个值填入坑中，同时这个位置形成一个新的坑

3.重复以上操作，直到left==right，然后把key值填入这个坑中，此时这个位置一定是坑，因为left和right永远有一个是坑

3.前后指针法

int partsort(int* a, int left, int right)
{int prev = left;int cur = left + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)//这里直接判断一下，相等就不交换，并且在判断条件 //的地方就更新prev{Swap(&a[prev], &a[cur]);}++cur;//cur就是一直往前走，直到结束，遇到相应位置才有操作，因此直接放到循环中}Swap(&a[keyi], &a[prev]);keyi = prev;return keyi;}

cur一直向后找小于key的位置

如果a【cur】< key

++prev，然后交换a【prev】和a【cur】

如果cur所在位置的值都比key小，那么cur和prev拉不开差距.++prev后和cur交换就是自身交换

        如果遇到比key大的值，就会拉开差距，此时如果cur遇到比key小的值，这个值就会和一个比key大的值交换，因为prev和cur原本中间隔着的都是大于key的值，++prev后再交换就会是这样的结果

 

这样相当于把大的往右推，小的往左推

 

cur走出数组结束，key与a【prev】交换即可 

注意点

        以上三种方法只是实现形式不同，时间复杂度是完全相同的，并且主逻辑的代码不需要更改，就是一个递归，只需要把部分排序修改即可