企业网站模板下载哪家好,网页设计素材螺蛳粉图,东莞建外贸网站好,哪些网站是做免费推广的算法原理
丛待排序的数列中选择一个基准值#xff0c;通过遍历数列#xff0c;将数列分成两个子数列#xff1a;小于基准值数列、大于基准值数列#xff0c;准确来说还有个子数列#xff1a;等于基准值即#xff1a;
算法图解
选出基准元素pivot#xff08;可以选择…算法原理
丛待排序的数列中选择一个基准值通过遍历数列将数列分成两个子数列小于基准值数列、大于基准值数列准确来说还有个子数列等于基准值即
算法图解
选出基准元素pivot可以选择最左侧元素设置两个指针Java中可看成是数组索引left和right,left指向数列最左边的元素right指向最右侧元素进行第一次遍历先丛right指针开始让其指向的元素和pivot作比较大于或等于则指针向左移动一个位置小于则停止移动等待left指针移动轮到left指针移动同样先让left指向的元素和pivot做比较小于或等于则指针向右移动大于则停止移动此时left和right都停止移动判断left和right是否在同一个位置否则交换位置元素。继续丛2开始直至left和right相交将pivot值与left指向的元素进行交换第一次遍历结束获得分区指针left。再将两个子数列按照1到6的步骤继续执行直至所有子数列排序完成。
算法实现
public class QuickSort {public void sort(int []arr){doSort(arr,0,arr.length-1);}public void doSort(int []arr,int left,int right){if(left right){return;}int partitionIndex partition(arr, left, right);doSort(arr,left,partitionIndex-1);doSort(arr,partitionIndex1,right);}/*** 右指针先往左移动* param arr* param left* param right* return*/public int partition(int []arr,int left,int right) {int startIndex left;int pivot arr[startIndex];while (left right) {while (left right arr[right] pivot) {right--;}while (left right arr[left] pivot) {left;}if (left right) {swap(arr, left, right);}}swap(arr, startIndex, left);return left;}private void swap(int arr[],int i,int j){int temp arr[i];arr[i] arr[j];arr[j] temp;}}测试 public static void main(String[] args) {int arr[] {9, 7, 1991, 27, -1, -10, 0,10,9,8,-1,27,-1, 2, 65, -100};new QuickSort().sort(arr);for (int i 0; i arr.length; i) {System.out.print(arr[i] \t);}}结果 分区实现2 /*** 左指针先往右移动* param arr* param left* param right* return*/public int partition(int []arr,int left,int right){int startIndex left;int pivot arr[startIndex];while (left right) {while (left right arr[left] pivot) {left;}while (left rightarr[right] pivot){right --;}if(left right){swap(arr,left,right);}}if(arr[left] pivot){swap(arr,startIndex,left-1);return left-1;}swap(arr,startIndex,left);return left;}
