快速排序(Quick Sort)

Dear 丶 2022-07-13 11:08 248阅读 0赞

一、算法原理

设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键 数据,然后将所有比它小的数据放到它前面,所有比它大的数据放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。

二、一般快速排序算法的步骤

  1. 设置两个变量i、j,排序开始的时候:i=0;j=N-1;
  2. 以第一个数组元素作为关键数据,赋值给key,即key=A[0];
  3. 从j开始向前搜索,即由后开始向前搜索(j- -),找到第一个小于key的值A[j],将A[i]和A[j]互换;
  4. 从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的值A[i],将A[i]和A[j]互换;
  5. 重复第3、4步,直到i=j;

三、快速排序算法的具体流程

LvCPlHp.png

  1. ①首先设置两个变量ij,分别指向序列的首尾元素
  2. ②该示例是以第一个元素为基准,从小到大进行排列。让j从后向前进行查询,直到找到第一个小于66的元素。
  3. 则将最后一个j指向的数23,和i指向的66交换位置。然后将i从前向后查询,直到找到第一个大于66的元素76

9glHPqV.png

  1. 7666位置互换。让j从后向前进行查询,直到找到第一个小于66的元素57

opR1t4Y.png

  1. 5766交换位置

JjlwD8L.png

  1. 然后将i从前向后查询,直到找到一个大于66的元素81

jIrQRXe.png

  1. 8166交换位置
  2. j从后向前查询,直到找到第一个小于66的元素26

WmRsFrP.png

  1. 2666交换位置
  2. 此时i,j都同时指向目标元素66
  3. 查找停止
  4. 所得到的序列就是第一趟排序的序列

uZ7seoL.png

  1. 第一趟排序结束,66左边的数都比66小,66右边的数都比66
  2. 再对66左边的序列和右边的序列分别递归调用上述过程

四、代码实现(Java)

  1. public class QuickSort {
  2. public static void main(String[] args) {
  3. int[] array = new int[]{57, 68, 59, 52, 72, 28, 96, 33, 24, 19};
  4. quickSort(array, 0, array.length-1);
  5. for(Integer i : array){
  6. System.out.print(i + " ");
  7. }
  8. }
  9. public static void quickSort(int[] numbers, int start, int end) {
  10. if (start < end) {
  11. int base = numbers[start]; // 选定的基准值(第一个数值作为基准值)
  12. int temp; // 记录临时中间值
  13. int i = start, j = end;
  14. do {
  15. while ((numbers[i] < base) && (i < end))
  16. i++;
  17. while ((numbers[j] > base) && (j > start))
  18. j--;
  19. if (i <= j) {
  20. temp = numbers[i];
  21. numbers[i] = numbers[j];
  22. numbers[j] = temp;
  23. i++;
  24. j--;
  25. }
  26. } while (i <= j);
  27. if (start < j){
  28. quickSort(numbers, start, j);
  29. }
  30. if (end > i){
  31. quickSort(numbers, i, end);
  32. }
  33. }
  34. }
  35. }

快速排序结果:19 24 28 33 52 57 59 68 72 96

发表评论

表情:
评论列表 (有 0 条评论,248人围观)

还没有评论,来说两句吧...

相关阅读

    相关 快速排序(Quick Sort)

    一、算法原理 设要排序的数组是A\[0\]……A\[N-1\],首先任意选取一个数据(通常选用数组的第一个数)作为关键 数据,然后将所有比它小的数据放到它前面,所有比它大

    相关 快速排序(Quick Sort)

    快速排序可以理解为:快速排序=挖坑填数+分治算法; 快速排序(Quick Sort)使用分治法(Divide and conquer)策略来把一个序列分为两个子序列,左右两个

    相关 快速排序(Quick-Sort)

    快速排序的主要思想是根据一个基准数(一般是待排序集中第一个元素)将一个待排序集分成左右两部分,其中左半部分数据集比右半部分数据集均要小或大,接下来,对左和右半部分按照相同的方法

    相关 快速排序(quick sort)

    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常