[回家作業] 排序 (三) 快速排序

周政輝

請根據上圖利用快速排序完成

彭煥宇

1. #include <iostream>
   
2. void swap(int *a, int *b){
   
3.     int temp = *a;
   
4.     *a = *b;
   
5.     *b = temp;
   
6. }
   
7. int Partition(int *arr, int front, int end){
   
8.     int pivot = arr[end];
   
9.     int i = front -1;
   
10.     for (int j = front; j < end; j++) {
    
11.         if (arr[j] < pivot) {
    
12.             i++;
    
13.             swap(&arr[i], &arr[j]);
    
14.         }
    
15.     }
    
16.     i++;
    
17.     swap(&arr[i], &arr[end]);
    
18.     return i;
    
19. }
    
20. void QuickSort(int *arr, int front, int end){
    
21.     if (front < end) {
    
22.         int pivot = Partition(arr, front, end);
    
23.         QuickSort(arr, front, pivot - 1);
    
24.         QuickSort(arr, pivot + 1, end);
    
25.     }
    
26. }
    
27. void PrintArray(int *arr, int size){
    
28.     for (int i = 0; i < size; i++) {
    
29.         std::cout << arr[i] << " ";
    
30.     }
    
31.     std::cout << std::endl;
    
32. }
    
33. int main() {
    
34. 
    
35.     int n = 9;
    
36.     int arr[] = {9, 4, 1, 6, 7, 3, 8, 2, 5};
    
37.     std::cout << "original:\t";
    
38.     PrintArray(arr, n);
    
39. 
    
40.     QuickSort(arr, 0, n-1);
    
41. 
    
42.     std::cout << "sorted:\t";
    
43.     PrintArray(arr, n);
    
44.     return 0;
    
45. }

複製代碼