排序

数组排序

• Arrays.sort(int a[])对数组所有元素进行排序，默认升序
• 使用Lamda表达式修改排序
• 升序：Arrays.sort(int a[]，(o1,o2)->o1-o2)
• 降序：Arrays.sort(int a[]，(o1,o2)->o2-o1)
• 对二维数组按第n个值排序
• Arrays.sort(nums,(o1,o2)->o1[n]-o2[n])可以应对复杂比较规则 ----------------------------------------
• 集合排序，使用与Arraylist，set等集合结构
• Collections.sort(List<>arr)
• 集合排序也可以使用lamada表达式重写比较器

  public static void main(String[] args) {
  		Scanner scan = new Scanner(System.in);
  		int[] num=new int[] {1,7,9,4,7,3};
  		int[][] nums=new int[][] {{1,4,9},{2,5,8},{6,9,45},{5,8,10},{0,1,7}};
  		Arrays.sort(num);
  		Arrays.sort(nums,(o1,o2)->(o1[0]-o2[0])-(o1[2]));//可以这样重写
  		//Arrays.sort(nums);报错
  		for (int i = 0; i < num.length; i++) {
  			System.out.print(num[i]+" ");
  		}
  		System.err.println("------num");
  		for (int i = 0; i < nums.length; i++) {
  			for (int j = 0; j < nums[i].length; j++) {
  				System.out.println(nums[i][j]+" ");
  			}
  			System.out.println();
  		}
  		scan.close();
  	}

快速排序(分治)

• 1.确定分界点，可以取q[l],q[l+r/2]或q[r]随机
• 2.调整区间，小于等于x的数在区间左边，大于等于x的数在区间右边

• 3.递归处理左右两端

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;//区间大小为0

    int i = l - 1, j = r + 1, x = q[l + r >> 1];//选定x为分界点
    while (i < j)//i在j左边，重复此过程
    {
        do i ++ ; while (q[i] < x);//i在区间左端，若当前所指向数小于x,则向右移
        do j -- ; while (q[j] > x);//j在区间右端，若当前所指向数大于x,则向左移
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);//递归处理左右两端
}