java数据结构与算法之快速排序详解
本文实例讲述了java数据结构与算法之快速排序。分享给大家供大家参考,具体如下:
交换类排序的另一个方法,即快速排序。
快速排序:改变了冒泡排序中一次交换仅能消除一个逆序的局限性,是冒泡排序的一种改进;实现了一次交换可消除多个逆序。通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
步骤:
1、从数列中挑出一个元素,称为 "基准"(pivot);
2、重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
3、递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(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--; } // 找到小于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程序设计有所帮助。
推荐阅读
-
Java排序算法之冒泡排序 博客分类: 算法common数据结构java java算法排序冒泡排序
-
Java排序算法之快速排序 博客分类: 数据结构commonjava算法more and more java算法快速排序
-
Java排序算法之简单选择排序 博客分类: 算法数据结构javacommon 算法java简单选择排序直接选择排序
-
java数据结构与算法之插入算法实现数值排序示例
-
java数据结构与算法之双向循环队列的数组实现方法
-
java数据结构与算法之奇偶排序算法完整示例
-
java数据结构与算法之noDups去除重复项算法示例
-
java数据结构与算法之插入算法实现数值排序示例
-
java数据结构与算法之奇偶排序算法完整示例
-
java数据结构与算法之双向循环队列的数组实现方法