C++ 快速排序算法

zltzlt

1. // 快速排序算法
   
2. 
   
3. #include <iostream>
   
4. using namespace std;
   
5. int a[1000] = {};
   
6. 
   
7. void qsort(int l, int r)
   
8. {
   
9.     int i = l, j = r, m = a[(l + r) / 2], temp;
   
10.     if (l >= r)
    
11.         return;
    
12.     do
    
13.     {
    
14.         while (a[i] < m)
    
15.             i++;
    
16.         while (a[j] > m)
    
17.             j--;
    
18.         if (i <= j)
    
19.         {
    
20.             temp = a[i];
    
21.             a[i] = a[j];
    
22.             a[j] = temp;
    
23.             i++;
    
24.             j--;
    
25.         }
    
26.     } while (i <= j);
    
27.     if (l < j)
    
28.         qsort(l, j);
    
29.     if (i < r)
    
30.         qsort(i, r);
    
31. }
    
32. 
    
33. int main()
    
34. {
    
35.     int n, i;
    
36.     cin >> n;
    
37.     for (i = 1; i <= n; i++)
    
38.         cin >> a[i];
    
39.     qsort(1, n);
    
40.     for (i = 1; i <= n; i++)
    
41.         cout << a[i] << " ";
    
42.     return 0;
    
43. }

复制代码

不太理解代码意思

William4869

就是取其中一个元素，正着遍历到不比这个元素小的，反着遍历到不比这个元素大的，交换，直到两边遍历相遇，
每轮都用来确定取出的元素的最终位置，并保证其左侧均比这个元素小，右边均比这个元素大

随便写一个{3,7,2,6,1,5,4}记为A[1...7]
i=1,j=7
取出6，正着比较i确定i=2时A[i]比6大，j=7时A[j]比6小，交换成{3,4,2,6,1,5,7}
继续发现i=4，A[i]不小于6，j=6,A[j]不大于6，交换成{3,4,2,5,1,6,7}
继续发现i=6，A[i]不小于6，j=5,A[j]不大于6，i>=j，两边遍历相遇，不用交换，i=6为6的最终位置，
第一轮结束后6左边的都比6小，右边的都比6大

然后对A[1...5],A[7...7]快排,循环下去就可以

大概就是这么个样子