java数据结构与算法之快速排序详解

java数据结构与算法之快速排序详解

本文实例讲述了java数据结构与算法之快速排序。分享给大家供大家参考，具体如下：

交换类排序的另一个方法，即快速排序。

快速排序：改变了冒泡排序中一次交换仅能消除一个逆序的局限性，是冒泡排序的一种改进；实现了一次交换可消除多个逆序。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

步骤:

1、从数列中挑出一个元素，称为 "基准"（pivot）；

2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

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

递归的最http://底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

算法实现代码如下：

package exp_sort;

public class QuickSort {

public static void Qsort(int array[], int left, int right) {

int pos;

if (left < right) {

pos = quickSort(array, left, right);

//递归排序

Qsort(array, left, pos - 1);

Qsort(array, pos + 1, right);

}

}

/**

* 一趟快速排序

*

* @param array

* @param left

* @param right

* @return

*/

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

int low, high;

int temp = array[left]; // 选择基准记录（枢纽元）

low = left;

high = right;

while (low < high) {

// high从右到左找小于temp的记录

while (low < high && array[high] >= temp) {

high--;

}

// 找到http://小于temp的记录则交换

if (low < high) {

array[low] = array[high];

low++;

}

// low从左到右找到大于temp的记录

while (low < high && array[low] < temp) {

low++;

}

// 找到大于temp的记录，则交换

if (low < high) {

array[high] = array[low];

high--;

}

}

//将游标放在当前位置，此时low=high

array[low] = temp;

return low;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };

Qsort(array, 0, 7);

for (int i = 0; i < array.length; i++) {

System.out.print(array[i] + " ");

}

System.out.println("\n");

}

}

枢纽元的选取：

1、基本的快速排序：选取地一个元素作为枢纽元。实际中应尽量避免将第一个元素作为枢纽元（极端情况是：初始状态是已排好序或者反序的）。

2、随机化快排序 :  随机的选取枢纽元。

3、平衡快排 : 三数中值分割法：枢纽元的最好选择是数组中的中值，该中值，即左端、右端和中心位置上的三个元素的中值（推荐）。

算法分析：该算法是在实践中最快的一种排序算法，它的平均运行时间是O(N log N)，该算法之所以快，主要是由于非常精炼和高度优化的内部循环。它的最坏情况的性能是O(N^2)，但是这种情况可以改变。快速排序是一种分治的递归算法。该算法比归并排序算法排序快。

1、最坏情况的分析

当枢纽元是最小元素时，此时就相当于是对整个数组进行递归排序，时间复杂度为：O(N^2)

2、最好情况的分析

枢纽元正好位于中间，此时是对两个子数组进行递归排序，时间复杂度是：O(N log N)，这和归并排序的分析完全相同。

3、平均情况的分析

时间复杂度是：O( N log N)

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。