软件下载类型网站怎么做,穹拓网站建设,网站建设属于什么服务,wordpress 背景基本思路
通过一趟排序将要排序的数据分割成独立的两部分#xff0c;其中一部分的所有数据都比另外一部分的所有数据都要小#xff0c;然后再按此方法对这两部分数据分别进行快速排序#xff0c;整个排序过程可以递归进行#xff0c;以此达到整个数据变成有序序列。 缺点其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。 缺点如果本来已经有序则退化为冒泡排序时间复杂度是n*n
步骤
1、选取一个基准元素key一般选择第一个元素 2、设两个指针left和right其中left指向数列的左端right指向数列的右端。 3、将right指向的数据和key作比较大于则指针移动继续比较小于则将和left指针指向的值进行替换 4、将left指向的数据和key作比较小于则指针移动继续比较大于则将和right指针指向的值进行替换 5、当left和right指向重合时则将key的值放在指针所指的位置 6、此时数组可以以key为中心点分为左、右子序列对左、右子序列进行上述步骤指导左右子序列仅为一个值时即完成排序
key选取的基准元素一般为第一个元素 left待排序数列左指针。 right待排序数列右指针。
package com.algorithm;public class QuickSort {public static void quick_sort(Integer[] array,int l,int r) {if(l r) {return ;}int key array[l];int left l;int right r;while (left right) {//处理right指针对应的值while(right left array[right] key) { //右指针对于的值大于key,则下标左移right --;}if(left right) {array[left] array[right]; //left和right不相等时将right指向的值赋予left指针指向的值挖坑填数。}//处理left指针对于的值while(right left array[left] key) {left ;}if(left right) {array[right] array[left];//left和right不相等时将left指向的值赋予right指针指向的值挖坑填数。}}if(left right) {array[left] key;}quick_sort(array,l,right-1); // 将左子序列继续递归调用quick_sort(array,right1,r); // 将右子序列继续递归调用}public static void main(String[] args) {Integer[] array new Integer[]{19,97,9,17,1,8,90,34,2};quick_sort(array,0,array.length-1);System.out.println(排序后结果);for(int arr:array) {System.out.print(arr,);}}
}
