朴素快速排序

朴素快速排序

本当迷

2022 年 02 月 12 日

1198 次浏览

暂无评论

823字数

算法认知学习语言

## 基本思想：

先选取一个“标尺”，用它把整个数组过一遍筛选，

把数组筛选成两部分：其左边的元素都小于“标尺”,其右边元素都大于“标尺”，

然后继续再筛选，直到左边下标 >= 右边下标 排序结束！

</div>

## 朴素快速排序代码：

```cpp
#include<bits/stdc++.h>
using namespace std;
int partition(int a[], int l, int r){
	int isFlag = a[l]; //数组最左端的值为分割值 
	int i = l, j = r+1;
	while(true){
		while(i<r && a[++i] < isFlag);
		while(j>0 && a[--j] > isFlag);
		if(i>=j)break;
		swap(a[i], a[j]);
	}
	swap(a[l], a[j]);
	return j;
}
void quick_sort(int a[], int l, int r){
	if(l < r){
		int mid = partition(a, l, r);
		quick_sort(a, l, mid-1);
		quick_sort(a, mid+1, r);
	}
}
int main() {
	int arr[] = {2, 4, 1, 3, 9, 6, 7, 8, 0, 5};
	quick_sort(arr, 0, 9);
	//输出排序后的数组 
	for(int i = 0; i < 10; i++){
		cout<<arr[i]<<" ";
	}
	return 0;
}

```

## 进步优化：

我们可以对“标尺”做文章，使“标尺”为范围之间的随机一个数。

## 模板：

```cpp
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

```

最后修改：2022 年 03 月 14 日