算法思路
Source
Edit
History

undefined

排序算法

1. 比较类排序

通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线形时间比较类排序

2. 非比较类排序

不通过比较来决定元素间的相对次序，他可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序

比较类排序
交换排序：冒泡排序、快速排序
插入排序：简单插入排序、希尔排序
选择排序：简单选择排序、堆排序
归并排序：二路归并排序、多路归并排序

非比较类排序：计数排序、桶排序、基数排序

选择排序：
每次找最小值，然后放到待排序数组的起始位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void selectSort(int array[], int left, int right) {
    if (left >= right) return;
    for (int i = left; i <= right-1; i++) {
        int minIndex = i;
        int minValue = array[minIndex];
        for (int j = i+1; j <= right; j++) {
            if (array[j] < minValue) {
                minIndex = j;
                minValue = array[j];
            }
        }
        array[minIndex] = array[i];
        array[i] = minValue;
    }
}

插入排序：
从前到后逐步构建有序序列；对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

1
2
3
4
5
6
7
8
9
10
11
12
void insertSort(int array[], int left, int right) {
    if (left >= right) return;
    for (int i = left+1; i <= right; i++) {
        int preIndex = i - 1;
        int curValue = array[i];
        while (preIndex >= 0 && curValue < array[preIndex]) {
            array[preIndex+1] = array[preIndex];
            preIndex--;
        }
        array[preIndex+1] = curValue;
    }
}

冒泡排序：
嵌套循环，每次查看相邻的元素如果逆序，则交换

1
2
3
4
5
6
7
8
9
10
void bubbleSort(int array[], int left, int right) {
    if (left >= right) return;
    for (int i = left; i <= right; i++) {
        for (int j = left; j <= right-i-1; j++) {
            if (array[j] > array[j+1]) {
                swap(array[j], array[j+1]);
            }
        }
    }
}

快速排序
数组取标杆pivot，将小元素放 pivot 左边，大元素放右侧，然后依次对左边和右边的子数组继续快排；以达到整个序列有序。

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
public static void quickSort(int[] array, int begin, int end) {
    if (end <= begin) return ;
    int pivot = partition(array, begin, end);
    quickSort(array, begin, pivot-1);
    quickSort(array, pivot+1, end);
}

static int partition(int[] a, int begin, int end) {
    // pivot: 标杆位置， counter：小于 pivot 的元素的个数
    int pivot = end, counter = begin;
    for (int i = begin; i < end; i++) {
        if (a[i] < a[pivot]) {
            int temp = a[counter]; a[counter] = a[i]; a[i] = temp;
            counter++;
        }
    }
    int temp = a[pivot]; a[pivot] = a[counter]; a[counter] = temp;
    return counter;
}
``

归并排序 -- 分治
1. 把长度为n的输入序列分成两个长度为n/2的子序列
2. 对这两个子序列分别采用归并排序
3. 将两个排序好的子序列合并成一个最终的排序序列
```java
public static void mergeSort(int[] array, int left, int right) {
    if (right <= left) return;
    int mid = (left + right) >> 1; // (left+right)/2

    mergeSort(array, left, mid);
    mergeSort(array, mid+1, right);
    merge(array, left, mid, right); 
}

public static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1]; // 中间数组
    int i = left, j = mid+1, k = 0;

    while (i <= mid && j <= right) {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }

    while (i <= mid) temp[k++] = arr[i++];
    while(j <= right) temp[k++] = arr[j++];

    for (int p = 0; p < temp.length; p++) {
        arr[left+p] = temp[p];
    }
}

总结：高级排序
归并和快排具有相似性，但步骤相反
归并：先排序左右子数组，然后合并两个有序子数组
快排：先调配出左右子数组，然后对于左右子数组进行排序

堆排序（Heap Sort） - 堆插入 O(logN), 取最大/小值O(1)

  1. 数组元素依次建立小顶堆
  2. 依次取堆顶元素，并删除
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
// 使用stl提供的容器
void heap_sort(int a[], int len) {
    std::priority_queue<int, std::vector<int>, greater<int>> q;
    for (int i = 0; i < len; i++) {
        q.push(a[i]);
    }
    for (int i = 0; i < len; i++) {
        a[i] = q.top();
        q.pop();
    }
}
// 不使用stl提供的容器
void heapify(int array[], int len, int i) {
    int left = 2*i+1, right = 2*i+2;
    int largest = i;
    if (left < len && array[left] > array[largest]) {
        largest = left;
    }
    if (right < len && array[right] > array[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(array[largest], array[i]);
        heapify(array, len, largest);
    }
}

void heapSort(int array[], int left, int right) {
    if (left >= right) return;
    int len = right - left + 1;
    for (int i = len/2-1; i >= 0; i--) {
        heapify(array, len, i);
    }
    for (int i = len-1; i >= 0; i--) {
        swap(array[0], array[i]);
        heapify(array, i, 0);
    }
}
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
static void heapify(int[] array, int length, int i) {
    int left = 2*i+1, right = 2*i+2;
    int largest = i;

    if (left < length && array[left] > array[largest]) {
        largest = left;
    }
    if (left < length && array[right] > array[largest]) {
        largest = right;
    }

    if (largest != i) {
        int temp = array[i]; array[i] = array[largest]; array[largest] = temp;
        heapify(array, length, largest);
    }
}

public static void heapSort(int[] array) {
    if (array.length == 0) return;

    int length = array.length;
    for (int i = length / 2 - 1; i >= 0; i--) {
        heapify(array, length, i);
    }
    for (int i = length - 1; i >= 0; i--) {
        int temp = array[0]; array[0] = array[i]; array[i] = temp;
        heapify(array, i, 0);
    }
}