快捷導(dǎo)航

C/C++實(shí)現(xiàn)快速排序算法的思路及原理解析

更新時(shí)間：2021年01月12日 10:35:29 作者：有人_295

這篇文章主要介紹了C/C++實(shí)現(xiàn)快速排序算法的思路及原理解析,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

快速排序

1. 算法思想

快速排序的基本思想：通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。

2. 實(shí)現(xiàn)原理

2.1、設(shè)置兩個(gè)變量 low、high，排序開始時(shí)：low=0，high=size-1。
2.2、整個(gè)數(shù)組找基準(zhǔn)正確位置，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面

默認(rèn)數(shù)組的第一個(gè)數(shù)為基準(zhǔn)數(shù)據(jù)，賦值給key，即key=array[low]。
因?yàn)槟J(rèn)數(shù)組的第一個(gè)數(shù)為基準(zhǔn)，所以從后面開始向前搜索（high–），找到第一個(gè)小于key的array[high]，就將 array[high] 賦給 array[low]，即 array[low] = array[high]。（循環(huán)條件是 array[high] >= key；結(jié)束時(shí) array[high] < key）
此時(shí)從前面開始向后搜索（low++），找到第一個(gè)大于key的array[low]，就將 array[low] 賦給 array[high]，即 array[high] = array[low]。（循環(huán)條件是 array[low] <= key；結(jié)束時(shí) array[low] > key）
循環(huán) 2-3 步驟，直到 low=high，該位置就是基準(zhǔn)位置。
把基準(zhǔn)數(shù)據(jù)賦給當(dāng)前位置。

2.3、第一趟找到的基準(zhǔn)位置，作為下一趟的分界點(diǎn)。
2.4、遞歸調(diào)用（recursive）分界點(diǎn)前和分界點(diǎn)后的子數(shù)組排序，重復(fù)2.2、2.3、2.4的步驟。
2.5、最終就會(huì)得到排序好的數(shù)組。

3. 動(dòng)態(tài)演示

在這里插入圖片描述

4. 完整代碼

三個(gè)函數(shù)
基準(zhǔn)插入函數(shù)：int getStandard(int array[],int low,int high)
（返回基準(zhǔn)位置下標(biāo)）
遞歸排序函數(shù)：void quickSort(int array[],int low,int high)
主函數(shù)：int main()

#include <stdio.h>
#include <stdlib.h>

void display(int* array, int size) {
  for (int i = 0; i < size; i++) {
    printf("%d ", array[i]);
  }
  printf("\n");
}

int getStandard(int array[], int i, int j) {
  // 基準(zhǔn)數(shù)據(jù)
  int key = array[i];
  while (i < j) {
    // 因?yàn)槟J(rèn)基準(zhǔn)是從左邊開始，所以從右邊開始比較
    // 當(dāng)隊(duì)尾的元素大于等于基準(zhǔn)數(shù)據(jù) 時(shí),就一直向前挪動(dòng) j 指針
    while (i < j && array[j] >= key) {
      j--;
    }
    // 當(dāng)找到比 array[i] 小的時(shí)，就把后面的值 array[j] 賦給它
    if (i < j) {
      array[i] = array[j];
    }
    // 當(dāng)隊(duì)首元素小于等于基準(zhǔn)數(shù)據(jù) 時(shí),就一直向后挪動(dòng) i 指針
    while (i < j && array[i] <= key) {
      i++;
    }
    // 當(dāng)找到比 array[j] 大的時(shí)，就把前面的值 array[i] 賦給它
    if (i < j) {
      array[j] = array[i];
    }
  }
  // 跳出循環(huán)時(shí) i 和 j 相等,此時(shí)的 i 或 j 就是 key 的正確索引位置
  // 把基準(zhǔn)數(shù)據(jù)賦給正確位置
  array[i] = key;
  return i;
}

void QuickSort(int array[], int low, int high) {
  // 開始默認(rèn)基準(zhǔn)為 low
  if (low < high) {
    // 分段位置下標(biāo)
    int standard = getStandard(array, low, high);
    // 遞歸調(diào)用排序
    // 左邊排序
    QuickSort(array, low, standard - 1);
    // 右邊排序
    QuickSort(array, standard + 1, high);
  }
}

// 合并到一起快速排序
// void QuickSort(int array[], int low, int high) {
//   if (low < high) {
//     int i  = low;
//     int j  = high;
//     int key = array[i];
//     while (i < j) {
//       while (i < j && array[j] >= key) {
//         j--;
//       }
//       if (i < j) {
//         array[i] = array[j];
//       }
//       while (i < j && array[i] <= key) {
//         i++;
//       }
//       if (i < j) {
//         array[j] = array[i];
//       }
//     }
//     array[i] = key;
//     QuickSort(array, low, i - 1);
//     QuickSort(array, i + 1, high);
//   }
// }

int main() {
  int array[] = {49, 38, 65, 97, 76, 13, 27, 49, 10};
  int size  = sizeof(array) / sizeof(int);

  // 打印數(shù)據(jù)
  printf("%d \n", size);
  QuickSort(array, 0, size - 1);
  display(array, size);

  // int size   = 20;
  // int array[20] = {0};         // 數(shù)組初始化
  // for (int i = 0; i < 10; i++) {    // 數(shù)組個(gè)數(shù)
  //   for (int j = 0; j < size; j++) { // 數(shù)組大小
  //     array[j] = rand() % 1000;  // 隨機(jī)生成數(shù)大小 0~999
  //   }
  //   printf("原來的數(shù)組：");
  //   display(array, size);
  //   QuickSort(array, 0, size - 1);
  //   printf("排序后數(shù)組：");
  //   display(array, size);
  //   printf("\n");
  // }

  return 0;
}