排序算法优化（二）

题目：

给你一个整数数组 nums，请你将该数组升序排列。

冒泡排序优化

概念：把最大的换到最后一位，第二大的换到倒数第二位；
冒泡写法：

冒泡原始写法

public int[] maopao(int[] nums){
    for(int i=0;inums[j]){
              int tmp = nums[i];
              nums[i] = nums[j];
              nums[j] = tmp;
            }
        }
    }
    return nums;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

优化方法一

//内循环处理，每次只交换一次，这种方法其实就是选择排序
public int[] maopao(int[] nums){
    for(int i=0;imax){
            int tmp = nums[i];
            nums[i] = nums[idx];
            nums[idx] = tmp;
        }
    }
    return nums;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

优化方法二

/对已经有序的序列停止排序
public static void MaoPao(int[] arr) {
		int length = arr.length;
		boolean flag = true;
		//外层循环控制轮数：
		for (int i = 0; i < length - 1; i++) {
			  //内存循环进行比较：
			  //如果内循环整个一轮下去，一次交换也没有发生，
              //说明此时0~length-1-i之间的元素都已经是有序(升序)的了，
			  // 而且我们也知道length-1-i~length-1之间的元素也是刚刚冒泡排序好的有序序列，
			  // 那么此时说明，整个数组其实都已经是有序的了，就没有必要再继续遍历和比较下去了。
			  for (int j = 0; j < length - 1 - i; j++) {
					if (arr[j] > arr[j + 1]) {
						  int temp = arr[j];
						  arr[j] = arr[j + 1];
						  arr[j + 1] = temp;
						  flag = false;
					}
			  }
			  //所以我们设置一个flag，如果内循环整个一轮下去，一次交换也没有发生的时候，flag为true，跳出所有循环；
			  if (flag) {
					break;
			  }
		}
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

上面是最原始的冒泡和对冒泡优化后的两种算法，极端情况下这两种算法在对数组排序后都会超时；这时候就要考虑同为交换排序的快速排序；

快速排序

快排原始写法

public void  quickSort(int[] nums,int left,int right) {
        if(left>=right){
            return;
        }
        int le = left;
        int ri = right;
        //getMid(nums,left,right);
        int povit = nums[left];

        while (le< ri) {
            while (povit <= nums[ri] && le < ri) ri--;
            swap(nums,le,ri);
            while (nums[le] <= povit && le < ri) le++;
            swap(nums,le ,ri);
        }
        nums[le] = povit;
        quickSort(nums,left,le-1);
        quickSort(nums,le+1,right);

    }
    public void swap(int[] nums,int a,int b){
        int tmp = 0;
        if(nums[a]>nums[b]){
            tmp = nums[a];
            nums[a] = nums[b];
            nums[b] = tmp;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

优化方法一

三数取中法
三数取中即在数据中取第一个数、最后一个数和中间一个数，在这三个数据得到一个中数，以这个中数作为标准值进行排序
优点：这种方法完美解决了当标准值过大或者过小时造成数据全在标准值的左边或者全在右边，从而使得快速排序退化为冒泡排序。
缺点：当数列特别大时这种三数取中的方法的效果会变小，因为可能取到的三个数都非常小，这种时候就需要多取一些值，比如采取9数取中法；
九数取中：把数组分为前中后三段，每段都采用三值取中得到三个值，然后再从这三个数中去中数作为标准值，这样既能避免标准值偏大或者偏小的情况又能避免数组过大时取到的中值不够均匀
代码实现：

//三数取中法
public void getMid(int[]nums ,int left,int right){
    int mid=(left+right)/2;
    if (nums[left]>nums[right])swap(nums,left,right);
    if (nums[mid]>nums[right]) swap(nums,mid,right);
    if (nums[left]>nums[mid]) swap(nums,left,mid);
}
public void swap(int[] nums,int a,int b){
    int tmp = 0;
    if(nums[a]>nums[b]){
        tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}
//优化后的三数取中法
public void  quickSort(int[] nums,int left,int right) {
    if(left>=right){
        return;
    }
    int le = left;
    int ri = right;
    getMid(nums,left,right);
    int povit = nums[left];
    System.out.println("povit="+povit);
    while (le< ri) {
        while (povit <= nums[ri] && le < ri) ri--;
        nums[le] = nums[ri];
        while (nums[le] <= povit && le < ri) le++;
        nums[ri] = nums[le];
    }
    nums[le] = povit;
    quickSort(nums,left,le-1);
    quickSort(nums,le+1,right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

优化方法二：

把交换改成赋值
在快速排序中只有最后一次交换是有效的，即之前的操作都是将较小值放在标准值的左边，较大值放在标准值右边；

public void  quickSort(int[] nums,int left,int right) {
    if(left>=right){
        return;
    }
    int le = left;
    int ri = right;
    int povit = nums[left];
    //防止里面while满足le