排序算法总结

插入排序

直接插入

insertion_sort

  • 插入排序(稳定)

  • 时间复杂度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
public class InsertionSort { 
	public static void main(String[] args) {
		//给出无序数组
		int arr[] = {72,6,57,88,60,42,83,73,48,85};
		//输出无序数组
		System.out.println(Arrays.toString(arr));
		//插入排序
		insertionSort(arr);
		//输出有序数组
		System.out.println(Arrays.toString(arr));
		
	}

	public static void insertionSort(int[] arr) {
		
		for(int i=1; i<arr.length; i++) {
			for(int j=i-1; j>=0; j--) {
				if(arr[j+1]<arr[j]) {
					int temp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = temp;
				}
			}
		}
	}
}

希尔排序

  • 希尔排序(不稳定)
  • 设置步长，分组插入排序

shellSort

  • 代码实现：
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
public class ShellSort {
	
	public static void main(String[] args) {
		//给出无序数组
		int arr[] = {72,6,57,88,60,42,83,73,48,85};
		//输出无序数组
		System.out.println(Arrays.toString(arr));
		//希尔排序
		shellSort(arr);
		//输出有序数组
		System.out.println(Arrays.toString(arr));
		
	}

	public static void shellSort(int[] arr) {
		//设置步长
		int gap = arr.length/2; 
		while(gap>0) {
			for(int j=gap; j<arr.length; j++) {
				int i=j;
				//插入排序
				while(i>=gap && arr[i-gap]>arr[i]) {
					int temp = arr[i-gap];
					arr[i-gap] = arr[i];
					arr[i] = temp;
					i -= gap;
				}
			}
			gap = gap/2;
		}
	}
}

选择排序

直接选择

selection_sort

  • 选择排序(不稳定)
  • 不断地选择剩余元素中的最小者
  • 时间复杂度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
29
30
public class SelectionSort {
	
	public static void main(String[] args) {
		//给出无序数组
		int arr[] = {72,6,57,88,60,42,83,73,48,85};
		//输出无序数组
		System.out.println(Arrays.toString(arr));
		//选择排序
		selectionSort(arr);
		//输出有序数组
		System.out.println(Arrays.toString(arr));
		
	}

	private static void selectionSort(int[] arr) {
		
		for(int i=0; i<arr.length; i++) {
			int min_index = i;
			for(int j=i+1; j<arr.length; j++) {
				if(arr[j] < arr[min_index]) {
					min_index = j;
				}
			}
			int temp = arr[min_index];
			arr[min_index] = arr[i];
			arr[i] = temp;
		}
	}

}

堆排序

heapSort

  • 堆排序(不稳定)
  • 时间复杂度 O(nlogn)
  • 空间复杂度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
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
public class HeapSort {
	
	public static void main(String[] args) {
		//给出无序数组
		int arr[] = {72,6,57,88,60,42,83,73,48,85};
		//输出无序数组
		System.out.println(Arrays.toString(arr));
		//堆排序
		heapSort(arr);
		//输出有序数组
		System.out.println(Arrays.toString(arr));
		
	}

    public static void heapSort(int[] arr) {
        int len = arr.length -1;
        for(int i = len/2 - 1; i >=0; i --){ //堆构造
            heapAdjust(arr,i,len);
        }
        while (len >=0){
        	//将堆顶元素与尾节点交换后，长度减1，尾元素最大
            swap(arr,0,len--);    
            //再次对堆进行调整
            heapAdjust(arr,0,len);    
        }
    }
 
    public static void heapAdjust(int[] arr,int i,int len){
    	int left,right,j ;
    	while((left = 2*i+1) <= len){    //判断当前父节点有无左节点（即有无孩子节点，left为左节点）
    		right = left + 1;  //右节点
    		j = left;   //j"指针指向左节点"
    		//右节点大于左节点
    		if(j < len && arr[left] < arr[right])    
    			//当前把"指针"指向右节点
    			j ++;     
    		//将父节点与孩子节点交换（如果上面if为真，则arr[j]为右节点，如果为假arr[j]则为左节点）
    		if(arr[i] < arr[j])    
    			swap(arr,i,j);
    		//说明比孩子节点都大，直接跳出循环语句
    		else         
    			break;
    		i = j;
    	}
    }
    
    public static void swap(int[] arr,int i,int len){
             
    	int temp = arr[i];
        arr[i] = arr[len];
        arr[len] = temp;
    }

}

交换排序

冒泡排序

bubble_sort

  • 冒泡排序(稳定)
  • 时间复杂度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 class TestBubbleSort {

	public static void main(String[] args) {
		//给出无序数组
		int arr[] = {72,6,57,88,60,42,83,73,48,85};
		//输出无序数组
		System.out.println(Arrays.toString(arr));
		//冒泡排序
		bubbleSort(arr);
		//输出有序数组
		System.out.println(Arrays.toString(arr));
		
	}

	public static void bubbleSort(int[] arr) {
		
		for(int i=0; i<arr.length; i++) {
			for(int j=1; j<arr.length-i; j++) {
				if(arr[j-1]>arr[j]) {
					int temp = arr[j-1];
					arr[j-1] = arr[j];
					arr[j] = temp;
				}
			}
		}
	}

}

快速排序

Quicksort-example

  • 快排 = 冒泡 + 分治 + 递归
  • 时间复杂度 O(nlogn)
  • 空间复杂度O(logn)
  • 代码实现：
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
64
65
public class TestQuickSort {
	
	private static int partition(int[] arr, int low, int high) {
		//指定左指针i和右指针j
		int i = low;
		int j = high;
		//将第一个数作为基准值，挖坑
		int x = arr[low];
		//使用循环实现分区操作
		while(i<j) {
			//1. 从右向左移动j, 找到第一个小于基准值的值
			while(arr[j] >= x && i<j) {
				j--;
			}
			//2. 将找到的数填入i的(坑)位置, i++
			if(i<j) {
				arr[i] = arr[j];
				i++;
			}
			//3. 从左向右移动i, 找到第一个大于等于基准值的值
			while(arr[i] <= x && i<j) {
				i++;
			}
			//4. 将找到的数填入j的位置, j--
			if(i<j) {
				arr[j] = arr[i];
				j--;
			}
		}
		//使用基准值填坑，此即基准值的最终位置
		arr[i] = x; // arr[j] = x;
		//返回基准值的位置索引
		return i;
	}
	
	private static void quickSort(int[] arr, int low, int high) {
		if(low < high) {//递归结束条件
			//分区操作，将一个数组分成两个分区，返回分区界限索引
			int index = partition(arr, low, high);
			//对左分区进行快排
			quickSort(arr, low, index-1);
			//对右分区进行快排
			quickSort(arr, index+1, high);
		}
		
	}
	
	public static void quickSort(int[] arr) {
		int low = 0;
		int high = arr.length - 1;
		quickSort(arr, low, high);
	}
	
	public static void main(String[] args) {
		//给出无序数组
		int arr[] = {72,6,57,88,60,42,83,73,48,85};
		//输出无序数组
		System.out.println(Arrays.toString(arr));
		//快速排序
		quickSort(arr);
		//输出有序数组
		System.out.println(Arrays.toString(arr));
		
	}
}

归并排序

mergeSort

  • 归并排序(稳定)
  • 递归 + 合并
  • 时间复杂度 O(nlogn)
  • 空间复杂度O(n) +O(logn)
  • 代码实现：
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
public class MergeSort {
	
	public static void main(String[] args) {
		//给出无序数组
		int arr[] = {72,6,57,88,60,42,83,73,48,85};
		//输出无序数组
		System.out.println(Arrays.toString(arr));
		//归并排序
		mergeSort(arr);
		//输出有序数组
		System.out.println(Arrays.toString(arr));
		
	}

	public static void mergeSort(int[] arr) {
		int low = 0;
		int high = arr.length - 1;
		mergeSort(arr, low, high);
	}

	private static void mergeSort(int[] arr, int low, int high) {
		
		if(low<high) {
			int mid = (low + high) / 2;
			//对左边的数组进行递归排序
			mergeSort(arr, low, mid);
			//对右边的数组进行递归排序
			mergeSort(arr, mid+1, high);
			//合并两个已排序的数组
			mergeArr(arr, low, mid, high);
		}
	}

	private static void mergeArr(int[] arr, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;// 左指针
        int j = mid + 1;// 右指针
        int k = 0;
        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[k++] = arr[j++];
        }
        // 把新数组中的数覆盖arr组
        for (int k2 = 0; k2 < temp.length; k2++) {
            arr[k2 + low] = temp[k2];
        }
			
	}

}

对比

排序总结