如何实现快速排序
本篇内容介绍了“如何实现快速排序”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
创新互联建站是一家朝气蓬勃的网站建设公司。公司专注于为企业提供信息化建设解决方案。从事网站开发,网站制作,网站设计,网站模板,微信公众号开发,软件开发,小程序设计,十余年建站对混凝土搅拌罐车等多个方面,拥有丰富的网站维护经验。
概述
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高!它是处理大数据最快的排序算法之一了。
算法步骤
从数列中挑出一个元素,称为 "基准"(pivot);
重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;
先来看一下分区操作:
原始数组:
我们把数组的第一个元素 ‘5’ 作为"基准",然后在基准后面第一个元素的位置定义两个指针 “i”、“j” 指针“i”从左至右移动,每移动一下,需要比较“i”位置元素与基准值的大小,如果小于基准值,则执行一次“swap”,即交换“i”,“j”这两个位置的元素的值;另外,每执行一次“swap”,“j”的值加一。
ok,“j”暂时不动,“i”往后移动,当“i”移动到“1”的位置时,
此时,“1”小于基准值“5”,需要执行一次“swap”,同时"j"加一
以此类推,当“i”移动到最右侧时,结果如下:
此时我们只需要,交换“基准值”和“j”的前一个位置的值(也就是交换5 和 2),就能达到”分区“的效果,
我看可以看到所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面;
仔细观察会发现,指针“i”用来扫描数组元素,指针“j”的左侧始终时比基准小的元素,这也是为什么基准值要与“j”前一个元素交换。
至此,一轮“分区”操作完成。
我们来看整个过程:
代码:
public static int[] sort(int[] arr) { return quickSort(arr, 0, arr.length - 1); } private static int[] quickSort(int[] arr, int left, int right) { if (left < right) { //分区 int partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex - 1); quickSort(arr, partitionIndex + 1, right); } return arr; } private static int partition(int[] arr, int left, int right) { int pivot = left; //指针 j int j = pivot + 1; for (int i = j; i <= right; i++) { if (arr[i] < arr[pivot]) { swap(arr, i, j); j++; } } swap(arr, pivot, j - 1); return j - 1; } private static void swap(int[] arr, int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; }
“如何实现快速排序”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!
文章标题:如何实现快速排序
网页网址:http://scyanting.com/article/jhsoed.html