快速排序算法原理与实现

1、快速排序算法的原理：想必大家都学过和用过冒泡排序，这应该是大家成为程序员道路上学的第一个算法，那么我们的快速排序算法其实是在冒泡排序的基础上的一个改进，快速排序算法是利用一趟快速排序，一趟快排一般都是取第一个数作为准基数进行排序，将一串数据分成两个部分。

第一部分都比准基数小，第二部分都比准基数大。

如：（——-第一部分——准基数——第二部分——），也就这样以准基数分成了两个部分，接下来这两个部分继续使用一趟快排（可以用递归的方法），以此类推，最后数据显示是从小到大的排列顺序。

2、快速排序步骤：

我们先建立一组数据:

（1）根据一趟快排的规则，我们先定下一个准基数，通常准基数都是数据的第一位也就是这里的数字12。

（2）然后一趟快排是先从下标6向左进行和准基数12的比较，比较完一个后，然后再从下标0向右进行和准基数12的比较。

（3）我们进行比较的规则和操作是：从下标6向左进行和准基数12的比较，只要遇到的数据小于准基数12的时候我们就将这个数和准基数12进行替换，然后再执行从下标0向右进行和准基数12的比较.

如：我们从下标6向左进行和准基数12的比较，20>12，不满足一趟快排的规则，寻找下一位，1<12,所以我们将下标0的值和下标5的值进行替换替换后的结果为：

（4）执行完上一步之后，我们再从下标0向右进行和准基数12的比较，这里的规则是只要遇到的数据大于准基数12的时候我们就将这个数和准基数12进行替换，和上面一步恰恰相反。

如：我们再从下标0向右进行和准基数12的比较，30>12，所以我们将下标1的值和下标5的值进行替换。

（5）从左到右查找和从右到左的查找，都是通过下标来查找的，只要它们两者下标不相遇就可以一直进行排序，直到相遇后第一次一趟快排结束，不过，总有一次会相遇的。好了，执行完上一步之后，基本的套路也就生成了，接下来继续执行（3），（4）步骤，直到排序完成。

第一趟排序完成的结果为：

从上面第一次一趟快排结果我们可以看出从准基数那里将数据分成的两个部分，前面那一部分，1，5，5，都比准基数要小，后面的16，30，20，则比准基数要大。但是这还不算完，我们明显的看到排序并非从小到大。所以说我们需要把这整一条数据分成1，5，5和16，30，20这两个条数据再次进行一趟快排（递归），以此类推，直到排出一条规矩的数据为止。

最后的结果为：

3、快速排序代码实现：

public class QuickSort {

public static void main(String[] args) {

int arr[] = {49、38、65、97、76、13、27、49};         

quickSort(arr, 0, 7);

System.out.println(Arrays.toString(arr));     

}      

public static void quickSort(int[] arr, int left, int right) {

if (left < right) {                        

int mid = partion(arr, left, right);

quickSort(arr, 0, mid – 1);

quickSort(arr, mid + 1, right);

}

}     

public static void swap(int[] arr, int l, int r) {         

int tmp = arr[l];

arr[l] = arr[r];

arr[r] = tmp;

}

public static int partion(int[] arr, int left, int right) {        

while (left < right) {

while (left < right && arr[left] <= arr[right]) {

right–;

}

if (left<right){

swap(arr, left, right);

}             

while (left < right && arr[left] <= arr[right]) {

left++;

}

if (left<right){

swap(arr, left, right);

}         

}

return left;

}}

扩展资料：

快速排序由冒泡排序演变而来，冒泡排序原理：

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3、针对所有的元素重复以上的步骤，除了最后一个。

4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

参考资料：百度百科-快速排序

基本原理

从序列中任选一个数作为“基准”；所有小于“基准”的数，都挪到“基准”的左边；所有大于等于“基准”的数，都挪到“基准”的右边。

在这次移动结束之后，该“基准”就处于两个序列的中间位置，不再参与后续的排序；针对“基准”左边和右边的两个子序列，不断重复上述步骤，直到所有子序列只剩下一个数为止。

1、选择“基准”，并将其从原始数组分离

先获取基准的索引值，再使用splice数组方法取出基准值。

Tips：该实例中， 基准的索引值 = parseInt（序列长度 / 2）。

Tips：splice方法会改变原始数组。例如，arr = [1, 2, 3]; 基准索引值为1，基准值为2，原始数组变为arr = [1, 3]。

2、遍历序列，拆分序列

与“基准”比较大小，并拆分为两个子序列，小于“基准”的数存储于leftArr数组当中，大于等于“基准”的数存储于rightArr数组当中。

Tips：当然，也可以将 小于等于“基准”的数存于leftArr，大于“基准”的数存于rightArr。

由于要遍历序列，将每一个数与“基准”进行大小比较，所以，需要借助for语句来实现

3、递归调用，遍历子序列并组合子序列的结果

定义一个函数，形参用于接收数组

function quickSort(arr) { }；

实现递归调用遍历子序列，用concat数组方法组合子序列的结果。

4、判断子序列的长度

递归调用的过程中，子序列的长度等于1时，则停止递归调用，返回当前数组。

扩展资料

一趟快速排序的算法是：

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）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。

参考资料：百度百科 快速排序法