mc做图的网站,狐表做网站,阳谷网站建设费用,富阳网站制作快速排序 对冒泡排序的一种改进#xff0c;若初始记录序列按关键字有序或基本有序#xff0c;蜕化为冒泡排序。使用的是递归原理#xff0c;在所有同数量级O(n longn) 的排序方法中#xff0c;其平均性能最好。就平均时间而言#xff0c;是目前被认为最好的一种内部排序方…快速排序 对冒泡排序的一种改进若初始记录序列按关键字有序或基本有序蜕化为冒泡排序。使用的是递归原理在所有同数量级O(n longn) 的排序方法中其平均性能最好。就平均时间而言是目前被认为最好的一种内部排序方法基本思想是通过一躺排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。三个指针: 第一个指针称为pivotkey指针(枢轴)第二个指针和第三个指针分别为left指针和right指针分别指向最左边的值和最右边的值。left指针和right指针从两边同时向中间逼近在逼近的过程中不停的与枢轴比较将比枢轴小的元素移到低端将比枢轴大的元素移到高端枢轴选定后永远不变最终在中间前小后大。需要两个函数① 递归函数 public static void quickSort(int[]n ,int left,int right)② 分割函数(一趟快速排序函数) public static int partition(int[]n ,int left,int right)JAVA源代码(成功运行)package testSortAlgorithm;public class QuickSort {public static void main(String[] args) {int [] array {49,38,65,97,76,13,27};quickSort(array, 0, array.length - 1);for (int i 0; i array.length; i) {System.out.println(array[i]);}}/*先按照数组为数据原型写出算法再写出扩展性算法。数组{49,38,65,97,76,13,27}* */public static void quickSort(int[]n ,int left,int right){int pivot;if (left right) {//pivot作为枢轴较之小的元素在左较之大的元素在右pivot partition(n, left, right);//对左右数组递归调用快速排序直到顺序完全正确quickSort(n, left, pivot - 1);quickSort(n, pivot 1, right);}}public static int partition(int[]n ,int left,int right){int pivotkey n[left];//枢轴选定后永远不变最终在中间前小后大while (left right) {while (left right n[right] pivotkey) --right;//将比枢轴小的元素移到低端此时right位相当于空等待低位比pivotkey大的数补上n[left] n[right];while (left right n[left] pivotkey) left;//将比枢轴大的元素移到高端此时left位相当于空等待高位比pivotkey小的数补上n[right] n[left];}//当left right完成一趟快速排序此时left位相当于空等待pivotkey补上n[left] pivotkey;return left;}}
