【数据结构周周练】030 快速排序算法原理详解及代码分享

妖狐艹你老母 2021-06-11 15:13 386阅读 0赞

## 一、快速排序 ##

### 1、快速排序简介 ###

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

### 2、算法思想及流程 ###

排序时，选定一个元素作为基准，比基准大的数据放到其右侧，比基准小的数据放到其左侧，对于分成的这两个部分继续使用该方法，我们默认每个部分的首元素为基准。对于每次排序，有如下流程

1.设定两个变量 low 与 high 用来访问数组，low表示每部分元素第一个数据，high表示每部分元素的最后一个数据。如果low < high ，循环做如下两个操作：

a、从右往左对数据进行比较，如果数据比基准大，找前一个数据进行比较，high - 1；如果数据比基准小，将该组元素中第一个元素换成该数据。

b、从左往右对数据进行比较，如果数据比基准小，找后一个数据进行比较，low + 1；如果数据比基准大，将该组元素中最后一个数据换成该数据。

2.将下标为low 的数据换为基准数据；

3.递归操作左边的子表；

4.递归操作右边的子表。

## 二、全部代码 ##

刚才上面是分析，，为了方便大家理解，我将每次排序的结果输出，接下来我将所有的代码分享一下。

#include<iostream>
    
    using namespace std;
    
    int arr[9] = { 45,57,12,31,1,60,92,71,87 };
    int i = 1;
    
    int Partition(int A[], int low, int high) {
    	int pivot = A[low];
    	while (low < high)
    	{
    		while (low < high && A[high] >= pivot)
    			--high;
    		A[low] = A[high];
    		cout << "【第" << i++ << "次快速排序结果】\t";
    		for (int i = 0; i < 9; i++)
    		{
    			cout << arr[i] << "\t";
    		}
    		cout << endl;
    		while (low < high && A[low] <= pivot)
    			++low;
    		A[high] = A[low];
    		cout << "【第" << i++ << "次快速排序结果】\t";
    		for (int i = 0; i < 9; i++)
    		{
    			cout << arr[i] << "\t";
    		}
    		cout << endl;
    	}
    	A[low] = pivot;
    	cout << "【第" << i++ << "次快速排序结果】\t";
    	for (int i = 0; i < 9; i++)
    	{
    		cout << arr[i] << "\t";
    	}
    	cout << endl;
    	return low;
    }
    
    void QuickSort(int A[], int low, int high) {
    	if (low<high)
    	{
    		int pivotPos = Partition(A, low, high);
    		QuickSort(A, low, pivotPos - 1);
    		QuickSort(A, pivotPos + 1, high);
    	}
    }
    
    void main() {
    	QuickSort(arr, 0, 8);
    	for (int i = 0; i < 9; i++) {
    		cout << "A[" << i << "] = " << arr[i] << endl;
    	}
    }

## 三、结果 ##

### 1、排序过程 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_36_color_9F9FD7_t_70][]

### 2、排序结果 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_19_color_F2FF1F_t_70][]

大家有什么问题在下面留言哦！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_36_color_9F9FD7_t_70]: /images/20210516/223af350be5341838f2102a97cca35bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_19_color_F2FF1F_t_70]: /images/20210516/ade9da096c034463878b3ad826837fe2.png