排序算法入门

[toc]

1、冒泡排序

  • 平均-时间复杂度：==O(n^2^)==
  • 最好-时间复杂度：==O(n)==
  • 最坏-时间复杂度：==O(n^2^)==
  • 空间复杂度：==O(1)==
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

// 冒泡排序【升序】
    public static int[] bubbleSort(int[] arr){

        // 控制比较次数
        for(int i=1;i<arr.length;i++){

            // 判断本轮是否发生过交换，若本轮无交换，则表示 已有序
            boolean isSwap = false;

            // 控制比较
            for(int j=arr.length-1;j>0;j--){

                // arr[j] > arr[j-1]时，交换2个元素
                if(arr[j]>arr[j-1]){
                    int tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tmp;
                    isSwap = true;
                }
            }

            if(!isSwap)break;
        }

        return arr;
    }

2、选择排序

  • 平均-时间复杂度：==O(n^2^)==
  • 最好-时间复杂度：==O(n^2^)==
  • 最坏-时间复杂度：==O(n^2^)==
  • 空间复杂度：==O( 1)==
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// 选择排序【升序】
    public static int[] selectSort(int[] arr){

        for(int i=1;i<arr.length;i++){
            // 每轮开始时，假设本轮的第一个元素为最小值
            int minIdx = i-1;

            // 通过循环找出最小的
            for(int j=i;j<arr.length;j++){
                // 将本轮无序区中的最小值与无序区的第一个值交换【找出实际的最小值】
                if(arr[j]<arr[minIdx]){
                    int tmp = arr[j];
                    arr[j] = arr[minIdx];
                    arr[minIdx] = tmp;
                }
            } 
        }

        return arr;
    }

3、插入排序

  • 平均-时间复杂度：==O(n^2^)==
  • 最好-时间复杂度：==O(n)==
  • 最坏-时间复杂度：==O(n^2^)==
  • 空间复杂度：==O( 1)==
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 插入排序【升序】

	 public static int[] insertSort(int[] arr){

        for(int i=1;i<arr.length;i++){
            
            for(int j=i;j>0;j--){
                
                if(arr[j] < arr[j-1]){
                    int tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tmp;
                }
            } 
        }
        return arr;
    }

4、希尔排序

  • 平均-时间复杂度：==O(n^1.3^)==
  • 最好-时间复杂度：==O(n)==
  • 最坏-时间复杂度：==O(n^2^)==
  • 空间复杂度：==O( 1)==

直接插入排序算法的一种更高效的改进版本。

原始序列：【2，1，3，5，7】

希尔排序-步骤：

  • 选取 增量 gap = 2，即：每偏移gap个元素，选取1个元素。第一次选出【2，3，7】
  • 将按照 gap 选出的 几个数进行 直接插入排序。
  • 减小增量 gap , 继续选取数字，继续将选出的数继续直接插入排序。
  • 以此类推，直到有序。
1
2
3



5、快速排序

原始序列：【3，5，2，1，19，14，32】

思路：

1、定义1个分治函数

2、定义1个快排函数，在快排函数的内部调用分治函数

3、在main函数中调用快排函数

  1. 分治函数
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
public static int partition(int[] arr,int left,int right){
    
    int povit = left;
    
    while(left<right){
        // 右边大则向前移动指针
        while(left<right && arr[right]>arr[pivot]){
            right--;
        }
        // 左边小则向后移动指针
        while(left<right && arr[left]<arr[pivot]){
            left++;
        }
        
        // 2个指针都停止时，交换
        if (arr[left] >= arr[right]) {
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
        }        
    }
    
    
    if (left == right) {
        int tmp = arr[left];
        arr[left] = arr[pivot];
        arr[pivot] = tmp;
    }
    
    return left;    
}

2、快排函数

1
2
3
4
5
6
7
8
9
public static void quickSort(int[] arr,int start, int end){
    
    if(start>=end)return;
    
    int pivot = partition(arr,start,end);
    
    quickSort(arr,start,pivot-1);
    quickSort(arr,pivot+1,end);
}

3、主函数

1
2
3
4
5
6
7
8
9
10
int[] arr1 = {3,5,2,1,19,14,32};

// 排序前:[3, 5, 2, 1, 19, 14, 32]
System.out.println(Arrays.toString(arr1));

// 快排
QuickSortDemo.quickSort(arr1,0,arr1.length-1);

// 排序后:[1, 2, 3, 5, 14, 19, 32]
System.out.println(Arrays.toString(arr1));

4、完整代码：

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
61
62
63
package quickSort;

public class QuickSortDemo {


    public static int partition(int[] arr, int left, int right) {
        /*
        *  分治的步骤：
        *       1、将分组的第一个元素,设置为基准
        *       2、left指向第一个元素，right指向最后一个元素
        *       3、当left < right 所指的元素时，进入循环：
        *       4、      当 left <= 基准时，不断 ++ , 直到遇见第一个 > 基准的数时停下
        *       5、      当 right > 基准时，不断 -- , 直到遇见第一个 < 基准的数时停下
        *       6、      left 和 right 都停下时，交换 left 和 right 所在的元素。
        *       7、如果left 和 right相遇，交换 【基准元素】与【相遇位置的元素】
        * */

        int pivot = left;

        while (left < right) {

            while (left < right&&arr[right] > arr[pivot]) {
                right--;
            }

            while (left < right&&arr[left] <= arr[pivot]) {
                left++;
            }



            if (arr[left] >= arr[right]) {
                int tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
            }
        }

        if (left == right) {
            int tmp = arr[left];
            arr[left] = arr[pivot];
            arr[pivot] = tmp;
        }

        // 返回分治完成后的基准下标
        return left;
    }


    public static void quickSort(int[] arr,int start, int end){

        if(start>=end)return;

        int pivot = partition(arr,start,end);

        quickSort(arr,start,pivot-1);

        quickSort(arr,pivot+1,end);


    }
}