目录

​​​

前言

一、快速排序的算法大致思想

二、代码

1.main.cpp主函数

2.QuickSort.cpp快速排序的函数

2.头文件

总结

前言

用C++实现的选择排序算法里的快速排序。

---

一、快速排序的算法大致思想

        确立一个基准，以此基准将数据分为小于基准的子表和大于基准的子表（该基准元素就在它最终的位置上，递归的对两个子表重复上述过程直至每一部分为空为止，所有元素都放在了它最终的位置上。）

二、代码

有两个源文件：main.cpp,QuickSort.cpp;两个头文件FunctionDef.h,AllStruct.h。

1.main.cpp主函数

对49，38，65，97，76，13，27，49进行快速排序；

#include 
using namespace std;

#include"FunctionDef.h"

int main() 
{
	Elemtype A[8] = { 49,38,65,97,76,13,27,49 };
	QuickSort(A, 0, 7);
	for (int i = 0; i < 8; i++)
	{
		cout << A[i]<< endl;
	}

	system("pause");
	return 0;
}

2.QuickSort.cpp快速排序的函数

参考的是王道书上的讲解

#include "FunctionDef.h"

void QuickSort(Elemtype A[], int low, int high)
{
    if (low < high)        //递归跳出条件
    {
        int pivotpos = Partition(A,low,high);        //一次划分
        QuickSort(A, low, pivotpos - 1);        //对小于枢纽的子表进行划分
        QuickSort(A, pivotpos + 1, high);        //对大于枢纽的子表进行划分
    }
}

int Partition(Elemtype A[], int low, int high)        //一次划分
{
    Elemtype pivot = A[low];        //将当前表中第一个元素设为基准，对表进行划分
    while (low < high)        //循环跳出条件
    {
        while (low < high && A[high] >=pivot)        
            high--;
        A[low] = A[high];        //将比枢纽（即基准元素）小的移到左边
        while (low < high && A[low] <= pivot)
            low++;
        A[high] = A[low];        //将比枢纽大的移到右边
    }
    A[low] = pivot;        //基准元素放到最终位置
    return low;        //返回存放枢纽的最终位置
}

2.头文件

FunctionDef.h声明函数的头文件

#pragma once
#include"AllStruct.h"

void QuickSort(Elemtype A[], int low, int high);
int Partition(Elemtype A[], int low, int high);        //划分 

AllStruct.h.h定义一些类型名或结构体的头文件

#pragma once
//各种类型或结构体的定义


typedef int Elemtype;		//指定用Elemtype代表int类型，Elemtype代表数据元素

---

总结

快速排序的空间复杂度和时间复杂度都与递归层数有关，它是内排序中平均性能最好的一种排序方式。