算法导论第7章快速排序

快速排序
 1 #include <stdint.h>
 2 #include <iostream>
 3 // QUICKSORT(A, p, r)
 4 // if p < r
 5 //     q = PARTITION(A, p, r)
 6 //     QUICKSORT(A, p, q - 1)
 7 //     QUICKSORT(A, q + 1, r)
 8 // To sort an entire array, the initial call is QUICKSORT(A, 1, A.length)
 9 
10 // PARTITION(A, p, r)
11 // x = A[r]
12 // i = p - 1
13 // for j = p to r - 1
14 //     if A[j] <= x
15 //         i = i + 1
16 //         exchange A[i + 1] with A[r]
17 // exchange a[i + 1] with A[r]
18 // return i + 1
19 
20 void swap(int64_t* A, uint64_t i, uint64_t j)
21 {
22     int64_t tmp = A[i];
23     A[i] = A[j];
24     A[j] = tmp;
25 }
26 
27 int64_t partition(int64_t* A, int64_t p, int64_t r)
28 {
29     int64_t x = A[r];
30     int64_t i = p;
31     for (int64_t j = p; j < r; j++)
32     {
33         if (A[j] <= x)
34         {
35             swap(A, i, j);
36             i++;
37         }
38     }
39     swap(A, i, r);
40     return i;
41 }
42 
43 void quicksort(int64_t* A, int64_t p, int64_t r)
44 {
45     if (p < r)
46     {
47         int64_t q = partition(A, p, r);
48         quicksort(A, p, q - 1);
49         quicksort(A, q + 1, r);
50     }
51 }
52 
53 void print_array(int64_t* A, int64_t n)
54 {
55     std::cout << "print array" << std::endl;
56     for (int64_t i = 0; i < n; i++)
57     {
58         std::cout << A[i] << " ";
59     }
60     std::cout << std::endl;
61 }
62 #include <stdio.h>
63 #include "7.1_quicksort.h"
64 
65 int main()
66 {
67     int64_t array[] = { 2, 8, 7, 1, 3, 5, 6, 4 };
68     print_array(array, 8);
69     quicksort(array, 0, 7);
70     print_array(array, 8);
71     getchar();
72     return 0;
73 }
快速排序