Board logo

標題: [回家作業] 排序 (三) 快速排序 [打印本頁]

作者: 周政輝    時間: 2018-7-14 15:26     標題: [回家作業] 排序 (三) 快速排序

[attach]4481[/attach]

請根據上圖利用快速排序完成
作者: 彭煥宇    時間: 2018-7-17 11:35

  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.     int n = 9;
  35.     int arr[] = {9, 4, 1, 6, 7, 3, 8, 2, 5};
  36.     std::cout << "original:\t";
  37.     PrintArray(arr, n);

  38.     QuickSort(arr, 0, n-1);

  39.     std::cout << "sorted:\t";
  40.     PrintArray(arr, n);
  41.     return 0;
  42. }
複製代碼





歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2