排序算法(一)

排序算法分类

排序算法可以分为两大类：比较排序和非比较排序
比较排序：可以分为交换排序，插入排序，选择排序和归并排序
交换排序：冒泡排序和快速排序
插入排序：简单插入排序、希尔排序
选择排序：简单选择排序、堆排序
归并排序：二路归并排序、多路归并排序
分比较排序：可以分为计数排序，桶排序和基数排序；
一共是11种排序；

题目

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

冒泡排序

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

冒泡写法：

//原始写法，每一遍都交换n次
public int[] maopao(int[] nums){
    for(int i=0;inums[j]){
              int tmp = nums[i];
              nums[i] = nums[j];
              nums[j] = tmp;
            }
        }
    }
    return nums;
}

//优化内循环，交换一次，每次只交换一次
public int[] maopao(int[] nums){
    for(int i=0;imax){
            int tmp = nums[i];
            nums[i] = nums[idx];
            nums[idx] = tmp;
        }
    }
    return nums;
}

//优化三 ，对已经有序的序列停止排序
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

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

快速排序

概念：选定一个标准值，比这个标准值大的放在右边，小的放在左边；

   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

简单插入排序

概念：使用双层for循环实现，外层for循环实现n+1的遍历（n是前面已经有序的数组，1是新增要排序的数据），内层for循环实现对插入位置的查找；
代码如下：

public void  chaRu(int[] nums){
		int l = nums.length;
		for(int i =0 ;i=0 && nums[j]>tmp){
				nums[j+1] = nums[j];
				j--;
				}
			nums[j+1] = tmp;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12

希尔排序

概念：是按照不同步长对元素进行插入排序，将整个有序序列分割成若干个子序列分别进行插入排序；
代码如下：

public void xier(int[] nums){
		int l = nums.length;
		for(int dk= l/2;dk>=1;dk = dk/2){
			for(int i =dk ;i=0 && nums[j]>tmp){
					nums[j+dk] = nums[j];
					j=j-dk;
					}
				nums[j+dk] = tmp;
			}
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

选择排序

原理：先扫描整个数组，已找到最小元素并将这个元素与第一个元素交换；然后从最第二个元素开始扫描找出最小元素与第二数交换；不断重复这个过程；
代码如下(不要和冒泡排序搞混了)：

public void xuanze(int[] nums){
		int l = nums.length;
		for(int i=0;i