现在的位置: 首页 > 算法 > 正文

快速排序是什么意思?有哪些步骤

2020年02月20日 算法 ⁄ 共 1461字 ⁄ 字号 评论关闭

  快速排序(英语:Quicksort),又称划分交换排序,简称快排,一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序 n 个项目要 O(n log n) 次比较。在最坏状况下则需要O(n2) 次比较,但这种状况并不常见。事实上,快速排序O(n log n) 通常明显比其他算法更快,因为它的内部循环可以在大部分的架构上很有效率地达成。

  快速排序步骤为:

  1.从数列中挑出一个元素,称为"基准"。

  2.重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区操作。

  3.递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

  4.递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代中,它至少会把一个元素摆到它最后的位置去。

  从上面的过程中可以看到:

  ①先从队尾开始向前扫描且当low < high时,如果a[high] > tmp,则high–,但如果a[high] < tmp,则将high的值赋值给low,即arr[low] = a[high],同时要转换数组扫描的方式,即需要从队首开始向队尾进行扫描了。   ②同理,当从队首开始向队尾进行扫描时,如果a[low] < tmp,则low++,但如果a[low] > tmp了,则就需要将low位置的值赋值给high位置,即arr[low] = arr[high],同时将数组扫描方式换为由队尾向队首进行扫描。

  ③不断重复①和②,知道low>=high时(其实是low=high),low或high的位置就是该基准数据在数组中的正确索引位置。

  按照上诉理论的代码如下:

  package com.nrsc.sort;

  public class QuickSort {

  public static void main(String[] args) {

  int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };

  quickSort(arr, 0, arr.length - 1);

  System.out.println("排序后:");

  for (int i : arr) {

  System.out.println(i);

  }

  }

  private static void quickSort(int[] arr, int low, int high) {

  if (low < high) {   // 找寻基准数据的正确索引   int index = getIndex(arr, low, high);   // 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序   quickSort(arr, 0, index - 1);   quickSort(arr, index + 1, high);   }   }   private static int getIndex(int[] arr, int low, int high) {   // 基准数据   int tmp = arr[low];   while (low < high) {   // 当队尾的元素大于等于基准数据时,向前挪动high指针   while (low < high && arr[high] >= tmp) {

  high--;

  }

  // 如果队尾元素小于tmp了,需要将其赋值给low

  arr[low] = arr[high];

  // 当队首元素小于等于tmp时,向前挪动low指针

  while (low < high && arr[low] <= tmp) {   low++;   }   // 当队首元素大于tmp时,需要将其赋值给high   arr[high] = arr[low];   }   // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置   // 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]   arr[low] = tmp;   return low; // 返回tmp的正确位置   }   }   以上就是有关快速排序的相关介绍,如要了解更多排序知识,请关注学步园。

抱歉!评论已关闭.