排序算法-Sorting Algorithm

发表于 | 分类于
字数统计: 925

Overview

Method Average Performance Best Performance Worst Performance Space Complexity Stability
Bubble Sort $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ Yes
Insertion Sort $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ Yes
Selection Sort $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ No
Merge Sort $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(n)$ Yes
Quick Sort $O(nlogn)$ $O(n^2)$ $O(nlogn)$ $O(logn)$ No
Heap Sort $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(1)$ No

Bubble Sort

  • 从左到右，比较相邻的数字，如果顺序相反则交换
  • 重复上述过程直到所有数字顺序一致
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public void bubbleSort(int[] A) {
    	while (true) {
    		boolean exchange = false;
    		for (int i = 0; i < A.length - 1; i++) {
    			if (A[i] > A[i + 1]) {
    				int tmp = A[i];
    				A[i] = A[i + 1];
    				A[i + 1] = tmp;
    				exchange = true;
    			}
    		}
    		if (!exchange) break;
    	}
    }

Insertion Sort

  • 从左到右，对于每个新的数字，把它插入到之前序列中它应在在位置
  • 把它插入位置右边的数字向右in-place移动
  • 重复上述过程直到遍历完所有数字
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public void insertionSort(int[] A) {
    	for (int i = 1; i < A.length; i++) {
    		int k = i - 1;
    		int tmp = A[i];
    		while (k >= 0 && A[k] > tmp) {
    			A[k + 1] = A[k];
    			k--;
    		}
    		A[k + 1] = tmp;
    	}
    }

Selection Sort

  • 找到数组中最小的数字，放在第一个位置
  • 找到数组中第二小的数字，放在第二个位置
  • 以此类推，直到所有数字被排序
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public void selectionSort(int[] A) {
    	int n = A.length;
    	for(int i = 0; i < n; i++) {
    		int minIndex = i;
    		for (int j = i; j < n; j++) {
    			if (A[j] < A[minIndex]) {
    				minIndex = j;
    			}
    		}
    		int tmp = A[i];
    		A[i] = A[minIndex];
    		A[minIndex] = tmp;
    	}
    }

Merge Sort

  • 思想：先局部有序，再整体有序
  • 把数组分为长度相等的两部分
  • 对这两个子数组使用merge sort
  • 把两个子数组合并成一个有序的数组
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public void mergeSort(int[] A) {
    	merge(A, new int[A.length], 0, A.length - 1);
    }

    private void merge(int[] A, int[] tmp, int l, int r) {
    	if (l >= r) return;
    	int mid = (r - l) / 2 + l;
    	merge(A, tmp, l, mid);
    	merge(A, tmp, mid + 1, r);
    	int i = l, j = mid + 1;
    	for (int k = l; k <= r; k++) {
    		if (i <= mid && (j > r || A[i] <= A[j])) {
    			tmp[k] = A[i++];
    		} else {
    			tmp[k] = A[j++];
    		}
    	}
    	for (int k = l; k <= r; k++) {
    		A[k] = tmp[k];
    	}
    }

Quick Sort

  • 思想：先整体有序，再局部有序
  • 从数组中选出一个pivot元素
  • 对数组进行partition，比pivot小的元素放在它前面，比pivot大的元素放在它后面
  • 对被pivot分成的两个子数组进行quick sort排序
    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
    private Random rand;
    public void quickSort(int[] A) {
    	rand = new Random();
    	partition(A, 0, A.length - 1);
    }
    private void partition(int[] A, int l, int r) {
    	if (l >= r) return;
    	int i = l;
    	int j = r;
    	int index = rand.nextInt(r - l + 1) + l;
    	int pivot = A[index];
    	while (i <= j) {
    		while (i <= j && A[i] < pivot) {
    			i++;
    		}
    		while (i <= j && A[j] > pivot) {
    			j--;
    		}
    		if (i <= j) {
    			int tmp = A[i];
    			A[i] = A[j];
    			A[j] = tmp;
    			i++;
    			j--;
    		}
    	}
    	partition(A, l, j);
    	partition(A, i, r);
    }

Heap Sort

  • 将数组建立为大根堆
  • 将堆顶元素与数组最后一个元素交换
  • 进行堆化维持堆结构
  • 重复第2，3步直到所有元素被排序
    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
    int n;
    public void heapSort(int[] A) {
    	buildMaxHeap(A);
    	n = A.length;
    	for (int i = n - 1; i > 0; i--) {
    		swap(A, 0, i);
    		n--;
    		shiftDown(A, 0);
    	}
    }
    private void buildMaxHeap(int[] A) {
    	for (int i = (n - 2) / 2; i >= 0; i--) {
    		shiftDown(A, i);
    	}
    }
    private void shiftDown(int[] A, int x) {
    	int maxIndex = x;
    	int left = x * 2 + 1;
    	int right = x * 2 + 2;
    	if (left < n && A[left] > A[maxIndex]) {
    		maxIndex = left;
    	}
    	if (right < n && A[right] > A[maxIndex]) {
    		maxIndex = right;
    	}
    	if (maxIndex != x) {
    		swap(A, x, maxIndex);
    		shiftDown(A, maxIndex);
    	}
    }
    private void swap(int[] A, int a, int b) {
    	int tmp = A[a];
    	A[a] = A[b];
    	A[b] = tmp;
    }