第十八章 快速排序法
::: hljs-center
目录
第十八章 快速排序法
●前言
●认识排序
●一、快速排序法是什么？
1.简要介绍
2.具体情况
3.算法分析
●二、案例实现
1.案例一
●总结
:::
前言
排序算法是我们在程序设计中经常见到和使用的一种算法，它主要是将一堆不规则的数据按照递增或递减的方式重新进行排序。在如今的互联网信息时代，随着大数据和人工智能的发展，大型企业的数据库中有亿级的用户数据量。因此对其进行处理，排序算法也就成为了其中必不可缺的步骤之一。
认识排序
排序功能对计算机领域而言，是一项非常重要而且普遍的工作。排序中数据的移动方式可分为直接移动和逻辑移动两种方式，直接移动是直接交换存储数据的位置，而逻辑移动并不会移动数据存储的位置，仅改变指向这些数据辅助指针的值。排序通常按照数据量的多少和所使用的内存，可分为内部排序和外部排序，数据量小可以全部加载到内存来进行排序的，就称为内部排序，大部分排序属于此类。数据量大而无法一次性加载到内存中，必须借助磁带，磁盘等辅助存储器进行排序的，则称为外部排序。随着数据结构科学的进步，如今，陆续被提出的冒泡排序法，选择排序法，插入排序法，合并排序法，快速排序法，堆积排序法，希尔排序法，基数排序法，直接合并排序法等等，它们各有其特色和其应用场合。并且在算法中，我们非常关注算法程序代码的时间复杂度和空间复杂度，因为它会直接体现出我们程序代码的执行效率以及编程人员的逻辑思维等等的综合能力。当数据量相当庞大时，排序算法所花费的时间就显得相当重要，排序算法的时间复杂度可分为最好情况、最坏情况以及平均情况。另外，对于任何的排序算法都会有数据交换的操作，数据互换位置会暂时用到一个额外的空间，这也是排序算法中空间复杂度要考虑到的问题，而在排序算法中所使用的额外空间越小，它的空间复杂度就越好。
一、快速排序法是什么？
1.简要介绍
快速排序法是由C.A.R.Hoare所提出来的一种排序方法。快速排序法又被称为分割交换排序法，是目前比较公认并且常用的最佳排序法，它使用到了分治法的思想，会先在数据中找到一个虚拟的中间值，并按此中间值将所有排序的数据分为两部分。其中小于中间值的放在左边，大于中间值的放在右边。再以分治法的思想以相同的方式去分别处理左右两边的数据，直到重复完成排序即可。
2.具体情况
假设有n项记录，R1,R2,R3,...,Rn，其键值为K1,K2,K3,...,Kn。
（1）先假设K为第一个键值。
（2）从左向右找出键值Ki，使得Ki>K。
（3）从右向左找出键值Kj，使得Kj<K。
（4）如果i<j，那么将Ki与Kj交换位置，并且回到步骤（2）。
（5）如果i>=j，那么将K与Kj交换位置，并且将j作为基准点把数据列划分为左右两个部分，然后对于左右部分再次执行（1）~（5）的相应步骤，直到左边键值等于右边键值为止。
用快速排序法对下面的10个数据进行从小到大的排序。具体情况如下图所示：
①当K=35时，Ki=42>K，Kj=23<K，此时i<j，所以将二者互换位置。具体情况如下图所示：
②当K=35时，Ki=79>K，Kj=18<K， 此时i<j，所以将二者互换位置。具体情况如下图所示：
③当K=35时，Ki=62>K，Kj=12<K，此时i>=j，所以将K与Kj互换位置，并且以j为基准点将数据列分为左右两个部分。具体情况如下图所示：
④经过上述步骤后，小于键值K的数据就被放在了左边，大于键值K的数据就被放在右边。具体情况如下图所示:
按照上述的排序过程继续对左右两部分分别排序，具体情况如下图所示：
3.算法分析
①快速排序法是不稳定排序法。 ②快速排序法平均运行时间最快的排序算法。 ③该排序法在最坏情况下空间复杂度为O(n)，在最好情况下空间复杂度为O(log2 ^ n)。 ④该排序法在最好情况和平均情况下时间复杂度为O(nlog2 ^ n)，在最坏情况下的时间复杂度为O(n ^ 2)。
二、案例实现
1.案例一
①范例情况：用快速排序法对32，5，24，55，40，81，17，48，25，71这十个数据元素进行从小到大的排序，并且输出排序过程中每次处理下的结果情况。 ②代码展示：
#include<iostream>
using namespace std;
#define size 10 //事先声明排序数据的个数
class quick {
public:
int data[size];
void showresult(){
for (int i = 0; i < size; i++)
cout <<" " << data[i];
cout << endl;
}
int num = 0;
void quick_start(int left,int right) {
int left_idx, right_idx;
int temp;
if (left<right)
{
left_idx = left + 1;
right_idx = right;
while (1)
{
//测试每次排序的中间过程情况
cout << "第" << num++ << "次排序:";
showresult();
//从左向右扫描，找出一个键值大于data[left]的数据元素
for (int i = left+1; i <= right; i++)
{
if (data[i]>data[left])
{
left_idx = i;
break;
}
left_idx++;
}
//从右向左扫描，找出一个键值小于data[left]的数据元素
for (int j = right; j >= left+1; j--)
{
if (data[j] < data[left])
{
right_idx = j;
break;
}
right_idx--;
}
//如果left_idx<right_idx，将二者交换位置
if (left_idx < right_idx){
temp = data[left_idx];
data[left_idx] = data[right_idx];
data[right_idx] = temp;
}
else {
break;
}
}
//如果left_idx>=right_idx
if (left_idx >= right_idx)
{
//将data[left]与data[right_idx]交换位置
temp = data[left];
data[left] = data[right_idx];
data[right_idx] = temp;
//以递归的方式继续进行左半的快速排序
quick_start(left,right_idx-1);
//以递归的方式继续进行右半的快速排序
quick_start(right_idx+1,right);
}
}
}
};
void text()
{
quick q;
cout << "请输入要排序的" << size << "个数据" << endl;
for (int i = 0; i < size; i++)
cin >> q.data[i];
cout << "排序前：" << endl;
q.showresult();
q.quick_start(0,size-1);
cout << "排序后：" << endl;
q.showresult();
}
int main()
{
text();
}
③结果展示：
总结
以上就是快速排序法的所有内容，其实从我们上面的代码中不难看出，快速排序法就是分治、冒泡、递归这些经典算法的结合应用。该排序算法启示我们，算法是可以通过像组装的方式来结合应用的，这样就可以去解决更复杂的问题。从而也说明了学习算法和数据结构，核心是去学它的思想和方法，并且用其来解决我们要去解决的问题。
<您的三连和关注是我最大的动力>
标签：right,八大,idx,C++,算法,排序,data,left From： https://blog.51cto.com/zhangzhichaoya/6037316