本文共 650 字，大约阅读时间需要 2 分钟。

快速排序是采用了分而治之的思想。所谓分而治之就是☞以一个数为基准，将序列中的其他数往他两边“扔”。以从小到大排序为例，比他小的都扔到他的左边，比他大的都扔到他的右边，然后左右两边再分别重复这个操作，不停地分，直到分到每一个分区的基准数的左边或者右边都只剩一个数为止，这时排序也就完成了。

所以快速排序的核心思想就是将小的往左“扔”，只要能实现这个，就与快速排序的思想吻合，从初学者的角度，小的往左扔大的往右扔，首先能想到的往往是最小的往前插，大的往后插，这确实是一个思路，但是我们知道，数组是不擅长插入的，这个思路虽然能够吻合快速排序的思想，但是实现起来就不是“快速”排序，而是“慢速排序”了。

所以这种方法不可行，于是就有了下面的舞动算法，这种算法的思想是用交换取代插入，大大提高了排序的算法的速度。

假设序列中有 n 个数，将这n个数放到数组中，舞动算法中一趟快速排序的算法

1 设置两个变量 i、j，排序开始的时候，i=0,j=n-1; 2 以数组第一个元素为关键数据，赋予变量key，即key = A[0]; 3 从 j 开始前搜索，即由后开始向前搜索（j–）,找到第一个小于key的值A[j],将A[j]与A[i]交换。 4 然后再从i开始向后搜索，即由前开始向后搜索（++i），找到第一个大于key的A[i],将A[i]和A[j]交换。 5 重复第三步和第四步，直到 i = j。此时就能确保序列中所有元素都与 key 比较过了，且key的左边全部比key小，key的右边全部比key大。

转载地址：https://m528964214.blog.csdn.net/article/details/89892547 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！