快排

太过爱你忘了你带给我的痛 2024-04-17 16:18 15阅读 0赞

import java.util.Arrays;
    public class kuaiPai {
        public static void main(String[] args) {
            int[] arr = new int[]{5, 3, 4, 1, 6, 322, 66, 2, 78};
            quickSort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr));
        }
     
        public static void quickSort(int[] arr, int start, int end) {
            //当开始位置小于结束位置时（数组有数据）  进行排序  也就是递归入口
            if (start < end) {
                //首先找到基准数  作为比较的标准数  取数组开始位置   从哪里开始  用哪个数当标准数 这个就是标准数
                int stard = arr[start];
                //记录需要进行排序的下标
                int low = start;
                int high = end;
     
                //循环比对比标准数大和小的数字
                while (low < high) {
                    //如果标准数小于右边的数字  把右边的游标卡尺向左移动
                    while (low < high && stard <= arr[high]) {
                        high--;
                    }
                    //如果标准数大于 右边的数字
                    //用低位数字替换右边数字
                    arr[low] = arr[high];
                    //如果左边的数字比标准数小
                    while (low < high && arr[low] <= stard) {
                        low++;
                    }
                    //如果左边的数字比标准数大
                    //用左边数字替换右边数字
                    arr[high] = arr[low];
                }
                //把标准数赋给高或者低所在的元素
                arr[low] = stard;
                //处理所有比标准数小的数字
                quickSort(arr, start, low);
                //处理所有比标准数大的数字
                quickSort(arr, low + 1, end);
            }
        }
    }

package sort;
    
    import java.util.*;
    
    public class Finder {
    	public static void main(String[] args) {
    		Finder f = new Finder();
    		int[] array = { 5, 7, 9, 2, 4, 6, 8, 10, 12, 11, 14, 15, 13 };
    		int re = f.findKthCore(array, 4, 0, array.length - 1);
    		System.out.println(re);
    	}
    
    	public int findKthCore(int[] a, int K, int left, int right) {
    		//if (left < right) {
    			int old_left = left;
    			int old_right = right;
    			int temp = a[left];
    			while (left < right) {
    				while (left < right && a[right] > temp) {
    					right--;
    				}
    				a[left] = a[right];
    				//注意：此处不能使用a[left++] = a[right];，因为当数组为1,3,5,4时（即第一个元素的位置是正确的时候，会出现问题）
    				while (left < right && a[left] < temp) {
    					left++;
    				}
    				a[right] = a[left];
    			}
    			a[left] = temp;
    			if (left == K - 1) {
    				return a[left];
    			} else if (left > K - 1) {
    				return findKthCore(a, K, old_left, left - 1);
    			} else {
    				return findKthCore(a, K, left + 1, old_right);
    			}
    		//}else
    		//	return a[left];
    	}
    }