C++快速排序的简单实现

曾经终败给现在 2022-05-13 05:30 168阅读 0赞

快速排序的基本算法思想十分简单，不断地取一个数，通过交换位置，将比这个数大的数放到右边，将比这个数小的数放到左边。

**如果一个数左边的数全部比它小，且右边的数全部比它大，那么它当前的位置，就是排序后的位置。**

而快速排序就是每次取一个数，然后通过交换位置找到它的排序后位置，最终所有的数都找到了自己的位置，从而实现排序完成。

![这里写图片描述][70]

图片摘自《C++并发编程实战》

**快速排序的基本步骤:**

1.  取区间的第一个数，通过交换位置，使得这个数左边的数小于自己，右边的数大于自己。也就是说该数找到了自己排序后的位置。
2.  第一步操作将区间分成了左右两个区间，然后分别在左右两个区间执行第一步的操作。

**实现代码如下：**

static int Partition(std::vector<int>& nums, int low, int high) {
      int pivote = nums[low];
    
      while (low < high) {
        while (low < high && nums[high] >= pivote) {
          --high;
        }
        std::swap(nums[low], nums[high]);
    
        while (low < high && nums[low] < pivote) {
          ++low;
        }
        std::swap(nums[low], nums[high]);
      }
    
      return low;
    }
    
    static void QuickSort(std::vector<int>& nums, int low, int high) {
      if (nums.empty()) {
        return;
      }
    
      if (low >= high) {
        return;
      }
    
      int pivote_index = Partition(nums, low, high);
      QuickSort(nums, low, pivote_index - 1);
      QuickSort(nums, pivote_index + 1, high);
    }
    
    void QuickSort(std::vector<int>& nums) {
      QuickSort(nums, 0, nums.size() - 1);
    }
    
    //---------------------------------------------------
    
    void PrintNums(const std::vector<int>& nums) {
      for (int num : nums) {
        std::cout << num << " ";
      }
      std::cout << std::endl;
    }
    
    int main() {
      std::vector<int> nums{ 1, 2, 3, 4, 5, 6, 7 };
      QuickSort(nums);
      PrintNums(nums);
    
      nums = { 9, 8, 7, 6, 5 };
      QuickSort(nums);
      PrintNums(nums);
    
      nums = { 3, 3, 4, 1, 2 };
      QuickSort(nums);
      PrintNums(nums);
    
      nums = { 234, 12, 235, 123, 2345, 123 };
      QuickSort(nums);
      PrintNums(nums);
    
      return 0;
    }

Partition()函数的作用就是，将区间的第一个数找到它排序后的位置，这个数将这个区间分成两部分，而这个数就是中轴。然后两个子区间继续执行Partition()。

int Partition(std::vector<int>& nums, int low, int high) {
      int pivote = nums[low];
    
      while (low < high) {
        while (low < high && nums[high] >= pivote) {
          --high;
        }
        std::swap(nums[low], nums[high]);
    
        while (low < high && nums[low] < pivote) {
          ++low;
        }
        std::swap(nums[low], nums[high]);
      }
    
      return low;
    }

Partition()将第一个值作为中轴，然后将比它小的值放到它的左边，比它的大的值放到它的右边。要实现这一功能必须**将该区间的每个值都和这个中轴值进行比较**。  
pivote这个数会不断的在low和high这两个位置交换，当其在low位置时，只能用high位置的数和它比较，当其在high位置时，只能用low位置的数和它比较。

最初pivote在位置low，然后和位置high的值进行比较，如果比它大，那么就应该和它交换位置。交换位置之后，pivote在high位置。 然后用位置low的值和pivote进行比较，如果该值比pivote大，那么将两个值交换。

[70]: /images/20220513/b49f38f3292c4105a63465b790c6b32c.png