转载

快速排序

概述

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,并且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性。

快速排序,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录继续进行排序,以达到整个序列有序的目的。

形象图示:

快速排序

步骤

  1. 选择一个基准元素,通常选择第一个元素或者最后一个元素

  2. 通过一趟排序将待排序的记录分割成独立的两部分,其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值均比基准值大

  3. 此时基准元素在其排好序后的正确位置

  4. 然后分别对这两部分记录用同样的方法继续进行排序,直到整个序列有序。

实例

原始数据:

选择 3 作为基准

第一轮

从右往左找比3小的,2符合,将2和3对调 2 5 2 6 3 对调一次,查找的方向反向,从左向右找比3大的,5符合,对调 2 3 2 6 5 再从右往左找比3小的,2符合,对调 2 2 3 6 5 一轮结束 

第二轮

对 [2 2] 采用同上的方式进行,得到 2 2 3 6 5 

第三轮

对 [6 5] 采用同上的方式进行,得到 2 2 3 5 6 

最终结果

代码实现(Java)

package com.coder4j.main.arithmetic.sorting;  public class Quick {      private static int mark = 0;      /**      * 辅助交换方法      *       * @param array      * @param a      * @param b      */     private static void swap(int[] array, int a, int b) {         if (a != b) {             int temp = array[a];             array[a] = array[b];             array[b] = temp;             // 找到符合的,对调             System.out.println("对调" + array[a] + "与" + array[b] + ",得到");             for (int i : array) {                 System.out.print(i + " ");             }             System.out.println();         }     }      /**      * 新一轮分隔      *       * @param array      * @param low      * @param high      * @return      */     private static int partition(int array[], int low, int high) {         int base = array[low];         mark++;         System.out.println("正在进行第" + mark + "轮分隔,区域:" + low + "-" + high);         while (low < high) {             while (low < high && array[high] >= base) {                 high--;                 System.out.println("从右往左找比" + base + "小的,指针变动:" + low + "-" + high);             }             swap(array, low, high);             while (low < high && array[low] <= base) {                 low++;                 System.out.println("从左往右找比" + base + "大的,指针变动:" + low + "-" + high);             }             swap(array, low, high);         }         return low;     }      /**      * 对数组进行快速排序,递归调用      *       * @param array      * @param low      * @param heigh      * @return      */     private static int[] quickSort(int[] array, int low, int heigh) {         if (low < heigh) {             int division = partition(array, low, heigh);             quickSort(array, low, division - 1);             quickSort(array, division + 1, heigh);         }         return array;     }      /**      * 快排序      *       * @param array      * @return      */     public static int[] sort(int[] array) {         return quickSort(array, 0, array.length - 1);     }      public static void main(String[] args) {         int[] array = { 3, 5, 2, 6, 2 };         int[] sorted = sort(array);         System.out.println("最终结果");         for (int i : sorted) {             System.out.print(i + " ");         }     }  }

测试输出结果:

正在进行第1轮分隔,区域:0-4 对调2与3,得到 2 5 2 6 3  从左往右找比3大的,指针变动:1-4 对调3与5,得到 2 3 2 6 5  从右往左找比3小的,指针变动:1-3 从右往左找比3小的,指针变动:1-2 对调2与3,得到 2 2 3 6 5  从左往右找比3大的,指针变动:2-2 正在进行第2轮分隔,区域:0-1 从右往左找比2小的,指针变动:0-0 正在进行第3轮分隔,区域:3-4 对调5与6,得到 2 2 3 5 6  从左往右找比6大的,指针变动:4-4 最终结果 2 2 3 5 6  

经测试,与实例中结果一致。

原文  http://segmentfault.com/a/1190000004400908
正文到此结束
Loading...