0%

快速排序

快速排序

基础知识

名称 : 快速排序

性质 : 不稳定的排序算法

用途 : 分治思路的排序

复杂度 : 时间 O(nlogn) 空间 O(1)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/************************************************************************
> File Name: quick_sort2.cpp
> Author: Lao Zhenyu
> Mail: LaoZhenyu_961112@163.com
> Created Time: 五 1/15 17:48:29 2021
************************************************************************/

#include <iostream>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
using namespace std;

void quickSort(vector<int> &arr, int left, int right){
if(left >= right) return;
int i,j,base;
base = arr[left];
i = left, j = right;
while(i < j){
while(arr[j] >= base && i < j)
j--;
while(arr[i] <= base && i < j)
i++;
if(i < j)
swap(arr[i], arr[j]);
}
arr[left] = arr[i];
arr[i] = base;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}



int main(){
vector<int> arr{1,3,2,6,5,4,9,7,8,};
quickSort(arr, 0, arr.size() - 1);
for(int n : arr){
cout << n << endl;
}
return 0;
}
-------------本文结束, 感谢您的阅读, 如有问题欢迎联系我-------------