排序-快速排序

 1 #include<iostream>
 2 using namespace std;
 3 
 4 void quickSort(int arr[], int L, int R)//L和R代表两个指针,分别指向首元素和尾元素
 5 {
 6     if (L>=R)    //递归出口
 7         return;
 8     int left = L;
 9     int right = R;
10     int pivot = arr[left];    //中枢,假定首元素为中枢
11     while (left<right)
12     {
13         //比中枢大的元素排到中枢轴的右边,小的排到右边
14         while (left<right&&arr[right]>=pivot)
15         {
16             right--;
17         }
18         if (left < right)
19         {
20             arr[left] = arr[right];
21         }
22         while (left<right&&arr[left]<=pivot)
23         {
24             left++;
25         }
26         if (left < right)
27         {
28             arr[right] = arr[left];
29         }
30         if (left >= right)
31         {
32             arr[left] = pivot;
33         }
34     }
35 
36     //对中枢轴左右序列继续快速排序
37     quickSort(arr, L, right - 1);
38     quickSort(arr, right + 1, R);
39 }
40 
41 int main()
42 {
43     int arr[] = { 1,3,2,5,8,1,3,2,11,10 };
44     int n = 10;
45     quickSort(arr, 0, 9);
46 
47     for (int i = 0; i < n; i++)
48     {
49         cout << arr[i] << endl;
50     }
51     system("pause");
52     return 0;
53 }

参考视频:https://www.bilibili.com/video/av62621532?t=534

上一篇:查找第k小的元素-减治法


下一篇:php – usort()排序算法如何工作?