目录
原理
实现方式
正常实现
理由
先从右到左，在从左到右
先从左到右，先从右到左
挖坑法
效率
优化
测试
代码
原理
快速排序是将最左侧的数字当作关键数字，将关键数字放在对应位置，且关键数字左侧均大于它，右侧均小于它，采用递归的形式左右执行递归
实现方式
正常实现
升序排序：
先从右往左
如果开始位置小于结束位置并且当前位置大于关键数字则继续往左查找
再从左往右
如果开始位置小于结束位置并且当前位置小于关键数字则继续往左查找
两个结束后，此时begin位置大于关键数字，end位置小于，交换begin与end即可实现将关键数字左右两侧满足条件
当begin<end时继续执行如上操作
注意：先从右往左再从左往右不能进行交换
理由
先从右到左，在从左到右
右侧先停，左碰到右，则右侧此时位置小于关键数字，左碰到右，可保证相遇位置数字小于关键数字
左侧先停，右碰到左此时左侧位置为上一轮交换后的位置，即左侧此时小于关键数字，右碰到左，可保证相遇位置数字小于关键数字
先从左到右，先从右到左
与上相反
挖坑法
取出最左侧的数据
进入循环
同样从右往左查找，但是比较的是当前位置和关键数字的值
效率
和堆排序，希尔排序为同一级别
排序100000个数，快排和希尔均只用了10几ms，而冒泡则用了30s
优化
1.
我们可以将第一个数的位置和最后一个数的位置取出，创建mid=(left+right)/2，关键数字则为第一个数，最后一个数和mid三者之间的中间值，将中间值和首元素进行交换即可
2.
当元素个数小于10时，插入排序效率比快排更高，我们可以在此时使用插入排序代替快排
测试
一百万个数据
通过比较后我们可以发现
挖坑法比普通快排快一些，但是差距不大
优化后确实会比没优化要稍微快上一些
代码
void swap(int* p1, int* p2) {
int a = *p1;
*p1 = *p2;
*p2 = a;
}
void insertsort(int* a, int sum) {//插排
int begin, end, tmp;
for (begin = 0; begin < sum - 1; begin++) {
tmp = a[begin + 1];
end = begin;
while (end >= 0) {
if (a[end] > tmp) {
a[end + 1] = a[end];
end--;
}
else
break;
}
a[end + 1] = tmp;
}
}
int findmid(int* a, int left, int right) {。。中间值
int mid = (left + right) / 2;
if (a[left] > a[mid]) {
if (a[mid] > a[right])
return mid;
else {
if (a[left] > a[right])
return right;
return left;
}
}
else {
if (a[left] > a[right])
return left;
else {
if (a[mid] > a[right])
return right;
return mid;
}
}
}
void normalquick(int* a, int left, int right) {//普通
if (left >= right)
return;
int begin = left, end = right, key = left;
while (begin < end) {
while (begin < end && a[end] >= a[key])
end--;
while (begin < end && a[begin] <= a[key])
begin++;
swap(&a[begin], &a[end]);
}
swap(&a[begin], &a[key]);
key = begin;
normalquick(a, left, key - 1);
normalquick(a, key + 1, right);
}
void quicksort(int* a, int left, int right) {//优化快排
if (left >= right)
return;
if (right - left + 1 < 10) {
insertsort(a + left, right - left + 1);
return;
}
int begin = left, end = right, key = findmid(a, left, right);
swap(&a[begin], &a[key]);
key = left;
while (begin < end) {
while (begin < end && a[end] >= a[key])
end--;
while (begin < end && a[begin] <= a[key])
begin++;
swap(&a[begin], &a[end]);
}
swap(&a[begin], &a[key]);
key = begin;
quicksort(a, left, key - 1);
quicksort(a, key + 1, right);
}
void quicksorthoare(int* arr, int left, int right) {//挖坑法
if (left >= right)
return;
int begin=left, end=right, key=arr[left];
while (begin < end) {
while (begin < end && arr[end] >= key)
end--;
arr[begin] = arr[end];
while (begin < end && arr[begin] <= key)
begin++;
arr[end] = arr[begin];
}
arr[begin] = key;
quicksorthoare(arr, left, begin - 1);
quicksorthoare(arr, begin + 1,right);
}
void shellsort(int* arr, int sum) {//希尔排序
int i, j, gap=sum, tmp,a;
while (gap > 1) {
gap = gap / 3 + 1;
for (i = 0; i < gap; i++) {
for (j = i; j < sum - gap; j+=gap) {
tmp = arr[j + gap];
a = j;
while (a >= 0) {
if (arr[a] > tmp) {
arr[a + gap] = arr[a];
a -= gap;
}
else
break;
}
arr[a + gap] = tmp;
}
}
}
}
void hoarequick(int* a, int left, int right) {//优化挖坑
if (left >= right)
return;
if (right - left + 1 < 10) {
insertsort(a + left, right - left + 1);
return;
}
int begin = left, end = right, key = findmid(a, left, right);
swap(&a[begin], &a[key]);
key = a[left];
while (begin < end) {
while (begin < end && a[end] >= key)
end--;
a[begin] = a[end];
while (begin < end && a[begin] <= key)
begin++;
a[end] = a[begin];
}
a[begin] = key;
hoarequick(a, left, begin - 1);
hoarequick(a, begin + 1, right);
}
