排序算法

发表于

排序

Bubble Sort 冒泡排序

定义：重复比较数组中相邻的元素，如果前一个元素比后一个元素大，则交换他们的位置，如此重复，直到将最大的元素放到最后；重复上述步骤，每一次都将前面未排序的最大元素已经放到最后；

助记码：

1
2
3
i∈[0,N-1)               //循环N-1遍
  j∈[0,N-1-i)           //每遍循环要处理的无序部分
    swap(j,j+1)          //两两排序（升序/降序）

代码实现：

JAVA：

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
public void bubble_sort(int arr[], int len) {
	int i, j, temp;
	for (i = 0; i < len - 1; i++)
		for (j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
}
//优化一
public static void bubbleSort(int[] arr) {
    int i, temp, len = arr.length;
    boolean changed;
    do {
      changed = false;
      len -= 1;
      for (i = 0; i < len; i++) {
        if (arr[i] > arr[i + 1]) {
          temp = arr[i];
          arr[i] = arr[i + 1];
          arr[i + 1] = temp;
          changed = true;
        }
      }
     // 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置
     // 所以下一次排序, 最后的元素可以不再考虑
     len --;
    } while (changed);
  }
//优化二：
  public static void bubbleSort2(Comparable[] arr) {
        int n = arr.length;
        int newn;
        do {
            newn = 0;
            for (int i = 1; i < n; i++)
                if (arr[i - 1].compareTo(arr[i]) > 0) {
                    swap(arr, i - 1, i);
                    // 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
                    newn = i;
                }
            n = newn;
        } while (newn > 0);
  }

Python:

1
2
3
4
5
6
7
8
def bubble_sorted(iterable):
    new_list = list(iterable)
    list_len = len(new_list)
    for i in range(list_len - 1):
        for j in range(list_len - 1, i, -1):
            if new_list[j] < new_list[j - 1]:
                new_list[j], new_list[j - 1] = new_list[j - 1], new_list[j]
    return new_list

时间复杂度：（{\displaystyle O(n^{2})}O(n^{2})）

我的理解：比较的次数越多，说明未排序的元素越少，所以第一次比较，比较的元素最多，交换的次数也是最多；当比较了 n - 2 次之后，只有最前面的元素没有排序，很显然这时已经完成排序操作啦。

Select Sort 选择排序

定义：找出数组中最小的元素，将它和数组的第一个元素交换位置，再次，在剩下的元素中找到最小的元素，将它和数组的第二个元素交换位置。

公共方法：

1
2
3
4
5
6
7
8
9
private static boolean less(Comparable v, Comparable w) {
   return (v.compareTo(w) < 0);
}
private static void exch(Comparable[] a, int i, int j) {
   Comparable swap = a[i];
   a[i] = a[j];
   a[j] = swap;
}

代码实现：

JAVA 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void sort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        int min = i; //最小元素的索引
        for (int j = i+1; j < N; j++) {
            //将 a[i] 和 a[i+1 .. N] 中最小的元素进行比较
            if (less(a[j], a[min])) {
                min = j;
            }
        }
         exch(a, i, min);
    }
}

Python 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def selection_sort(L):
    N = len(L)
    exchanges_count = 0
    for i in range(N-1):
        min_index = i
        for j in range(i+1, N):
            if L[min_index] > L[j]:
                min_index = j
        if min_index != i:
            L[min_index], L[i] = L[i], L[min_index]
        exchanges_count += 1
        print('iteration #{}: {}'.format(i, L))
    print('Total {} swappings'.format(exchanges_count))
    return L
testlist = [17, 23, 20, 14, 12, 25, 1, 20, 81, 14, 11, 12]
print('Before selection sort: {}'.format(testlist))
print('After selection sort:  {}'.format(selection_sort(testlist)))

自己的理解：

  • 在数组中找到最小的元素，如何实现呢？ 将数组中的元素两两进行比较，确定最小元素的索引；
  • 将最小的元素放到数组的起始位置；如何实现呢？ 将最小元素的索引与第一个元素进行交换；
  • 重复上述步骤；

Insert Sort 插入排序

定义：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

代码实现：

1
2
3
4
5
6
7
8
9
10
public static void InsertSort(Comparable[] a) {
    int N = a.length;
    for (int i = 1; i < N; i++) {
        //将 a[i] 插入到 a[i -1]、a[i - 2]、a[i - 3]... 之中
        //寻找元素 a[i] 合适的插入位置
        for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
            exch(a, j, j - 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 void sort(Comparable[] arr){
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // 寻找元素arr[i]合适的插入位置
            // 写法1
//            for( int j = i ; j > 0 ; j -- )
//                if( arr[j].compareTo( arr[j-1] ) < 0 )
//                    swap( arr, j , j-1 );
//                else
//                    break;
            // 写法2
//            for( int j = i; j > 0 && arr[j].compareTo(arr[j-1]) < 0 ; j--)
//                swap(arr, j, j-1);
            // 写法3
            Comparable e = arr[i];
            int j = i;
            for( ; j > 0 && arr[j-1].compareTo(e) > 0 ; j--)
                arr[j] = arr[j-1];
            arr[j] = e;
        }
    }

WIKI 写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void insertionSort(int[] array) {
		for (int i = 1; i < array.length; i++) {
			int key = array[i];
			int j = i - 1;
			while (j >= 0 && array[j] > key) {
				array[j + 1] = array[j];
				j--;
			}
			array[j + 1] = key;
		}
}
//将arr[i] 插入到arr[0]...arr[i - 1]中
	public static void insertion_sort(int[] arr) {
		for (int i = 1; i < arr.length; i++ ) {
			int temp = arr[i];
			int j = i - 1;  
    //如果将赋值放到下一行的for循环内, 会导致在第10行出现j未声明的错误
			for (; j >= 0 && arr[j] > temp; j-- ) {
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = temp;
		}
	}

算法的痛点：在遍历的同时也在执行交换操作。

改进：提前终止内层循环。针对近乎有序的数组，排序效率更高。

算法改进：

  • 利用多次交换相邻元素减少元素的赋值操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public void insertSort(T arr[], int N) {
        for(int i = 1; i < N; i++) {
            T e = arr[i];
            int j;// j 保存元素 e 应该插入的位置
            for (j = i; j > 0 && arr[j - 1] > e; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = e;
        }
    }
    public void insertSort(T arr[], int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            T e = arr[i];
            int j;
            for(j = i; j > l && arr[j - 1] > e; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = e;
        }
    }

  • InsertX 先将大元素移动到最后，减少交换的元素。

    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
    /**
      * Rearranges the array in ascending order, using the natural order.
      * @param a the array to be sorted
      */
     public static void sort(Comparable[] a) {
         int n = a.length;
      
         // put smallest element in position to serve as sentinel
         int exchanges = 0;
         for (int i = n-1; i > 0; i--) {
             if (less(a[i], a[i-1])) {
                 exch(a, i, i-1);
                 exchanges++;
             }
         }
         if (exchanges == 0) return;
      
      
         // insertion sort with half-exchanges
         for (int i = 2; i < n; i++) {
             Comparable v = a[i];
             int j = i;
             while (less(v, a[j-1])) {
                 a[j] = a[j-1];
                 j--;
             }
             a[j] = v;
         }
      
         assert isSorted(a);
     }

  • BinaryInsertion 二分插入

    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 BinaryInsertion {
        // This class should not be instantiated.
        private BinaryInsertion() { }
        /**
         * Rearranges the array in ascending order, using the natural order.
         * @param a the array to be sorted
         */
        public static void sort(Comparable[] a) {
            int n = a.length;
            for (int i = 1; i < n; i++) {
                // binary search to determine index j at which to insert a[i]
                Comparable v = a[i];
                int lo = 0, hi = i;
                while (lo < hi) {
                    int mid = lo + (hi - lo) / 2; 
                    if (less(v, a[mid])) hi = mid;
                    else                 lo = mid + 1;
                }
                // insetion sort with "half exchanges"
                // (insert a[i] at index j and shift a[j], ..., a[i-1] to right)
                for (int j = i; j > lo; --j)
                    a[j] = a[j-1];
                a[lo] = v;
            }
            assert isSorted(a);
        }

    我的理解：在已知序列中从后向前扫描，对于未知元素找到合适的位置插入，同时将已知序列的元素向后移动一位。

Shell Sort 希尔排序

定义：使数组中任意间隔为 h 的元素都是有序的。

希尔排序是对插入排序的改进；插入元素是相邻元素进行移动，希尔排序是交换不相邻元素以对数组的局部进行排序，并最终利用插入排序将局部有序的数组进行排序。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
     * Rearranges the array in ascending order, using the natural order.
     * @param a the array to be sorted
     */
public static void sort(Comparable[] a) {
    int n = a.length;
    // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ... 
    int h = 1;
    while (h < n/3) h = 3*h + 1; 
    while (h >= 1) {
        // h-sort the array
        for (int i = h; i < n; i++) {
            //将 a[i] 插入到 a[i - h], a[i - 2 * h] ... 之中
            for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                exch(a, j, j-h);
            }
        }
        assert isHsorted(a, h); 
        h /= 3;
    }
    assert isSorted(a);
}

WIKI 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void shellSort(int[] arr) {
	int gap = 1, i, j, len = arr.length;
	int temp;
	while (gap < len / 3)
		gap = gap * 3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
	for (; gap > 0; gap /= 3)
		for (i = gap; i < len; i++) {
			temp = arr[i];
			for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
				arr[j + gap] = arr[j];
			arr[j + gap] = temp;
		}
}

优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void sort(Comparable[] arr){
     int n = arr.length;
     // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
     int h = 1;
     while (h < n/3) h = 3*h + 1;
     while (h >= 1) {
         // h-sort the array
         for (int i = h; i < n; i++) {
             // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
             Comparable e = arr[i];
             int j = i;
             for ( ; j >= h && e.compareTo(arr[j-h]) < 0 ; j -= h)
                 arr[j] = arr[j-h];
             arr[j] = e;
         }
         h /= 3;
     }
 }

我的理解：将数组分为步长为 h 的序列，分别对他们进行插入排序；同时不断降低 步长 h 的幅度，在对数组进行插入排序，最后进行到步长为 1 时，说明数组已经排好序啦。

Merge Sort 归并排序

定义：先递归的将数组分成两半分别排序，然后将结果归并起来。体现的是 “分治” 的思想。

思想：指的是将两个已经排序的序列合并成一个序列的操作；

1
2
3
4
// Merge Sort是我们学习的第一个O(nlogn)复杂度的算法
// 可以在1秒之内轻松处理100万数量级的数据
// 注意：不要轻易尝试使用SelectionSort, InsertionSort或者BubbleSort处理100万级的数据
// 否则，你就见识了O(n^2)的算法和O(nlogn)算法的本质差异：）

递归法（Top-down）

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  4. 重复步骤3直到某一指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

迭代法（Bottom-up）
原理如下（假设序列共有 { n} n个元素）：

  1. 将序列每相邻两个数字进行归并操作，形成 ceil(n/2) 个序列，排序后每个序列包含两/一个元素
  2. 若此时序列数不是1个则将上述序列再次归并，形成 ceil(n/4)个序列，每个序列包含四/三个元素
  3. 重复步骤2，直到所有元素排序完毕，即序列数为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
//递归的调用
public void mergeSort(T arr[], int l, int r) {
    if (l >= r) return;
    //针对较少的数组元素进行插入排序
    //if (r -l >= 15) {
      //  insertSort(arr, l, r);
        //return;
    //}
    int mid = l + (r - l)/ 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid+1, r);
    //如果要排序的数组是近乎有序的话，加上下面的判断
    //if (arr[mid] > arr[mid +a]) {}
    merge(arr, l, mid, r);
}
//将 arr[l..mid] 和 arr[mid+1 ... r] 两部分进行归并
public void merge(T arr[], int l, int mid, int r) {
    T aux[r - l + 1];
    for (int i = l; i <= r; i++) {
        aux[i - l] = arr[i];
    }
    // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
    int i = l, j = mid + 1;
    for(int k = l; k <= r; k++) {
        if (i > mid) {// 如果左半部分元素已经全部处理完毕
            arr[k] = aux[j - l];
            j++;
        } else if (j > r) {// 如果右半部分元素已经全部处理完毕
            arr[k] = aux[i - l];
            i++;
        } else if (aux[i - l] < aux[j - l]) {// 左半部分所指元素 < 右半部分所指元素
            arr[k] = aux[i - l];
            i++;
        } else {// 左半部分所指元素 >= 右半部分所指元素
            arr[k] = aux[j - l];
            j++;
        }
    }
}

归并排序算法的几种优化：

  • 原地归并 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    // stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
        assert isSorted(a, lo, mid);
        assert isSorted(a, mid+1, hi);
      
        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k]; 
        }
      
        // merge back to a[]
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)              a[k] = aux[j++];
            else if (j > hi)               a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else                           a[k] = aux[i++];
        }
      
        // postcondition: a[lo .. hi] is sorted
        assert isSorted(a, lo, hi);
    }

  • 自顶向下的归并排序

    1
    2
    3
    4
    5
    6
    7
    8
    // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

  • 自底向上的归并排序: 以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
    //迭代
    /**
         * Rearranges the array in ascending order, using the natural order.
         * @param a the array to be sorted
         */
        public static void sort(Comparable[] a) {
            int n = a.length;
            Comparable[] aux = new Comparable[n];
            //遍历元素
            for (int len = 1; len < n; len *= 2) {
                //要归并的元素的起始位置
                for (int lo = 0; lo < n-len; lo += len+len) {
                    int mid  = lo+len-1;
                    int hi = Math.min(lo+len+len-1, n-1);
                    merge(a, aux, lo, mid, hi);
                }
            }
            assert isSorted(a);
        }
    //改良版（同上）
    public void mergeSortBU(T arr[], int n) {
        for (int sz = 1; sz <= n; sz += sz) {
            for (int i = 0; i + sz < n; i += sz + sz) {
                 //对 arr[i ... i + len - 1] 和 arr[i + len ... i + 2 * len - 1]进行归并
                 merge(arr, i, i + sz - 1, Math.min(i + sz + sz -1, n - 1));
            }
        }
    }

我的理解：归并排序的思想是将数组复制一份，将复制出来的数组分为两半，将前后两部分中每一个元素进行比较，将较小的元素放到原数组中。

Quick Sort 快速排序

定义：首先找到 “切分” 元素，将数组分为两部分，将左右两部分分别排序，当两个数组都是有序时整个数组就是有序的。

JAVA 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Rearranges the array in ascending order, using the natural order.
 * @param a the array to be sorted
 */
public static void sort(Comparable[] a) {
    StdRandom.shuffle(a);
    sort(a, 0, a.length - 1);
    assert isSorted(a);
}
// quicksort the subarray from a[lo] to a[hi]
private static void sort(Comparable[] a, int lo, int hi) { 
    if (hi <= lo) return;
    int j = partition(a, lo, hi);
    sort(a, lo, j-1);
    sort(a, j+1, hi);
    assert isSorted(a, lo, hi);
}

  • 切分

    1. 随意取 a[0] 作为切分元素

    2. 从数组的左边开始向右扫描直到找到一个大于等于它的元素

    3. 再从数组的右边向左扫描直到找到一个小于等于它的元素

    4. 交换它们的位置。

    5. 如此继续

      …

    6. 我们只需要将切分元素 a[0] 和左子数组最右侧的元素a[j] 交换，然后返回 j 即可。

  • 随机快速排序：

    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
    // partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
    // and return the index j.
    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        Comparable v = a[lo];
        while (true) { 
      
            // find item on lo to swap
            while (less(a[++i], v)) {
                if (i == hi) break;
            }
      
            // find item on hi to swap
            while (less(v, a[--j])) {
                if (j == lo) break;      // redundant since a[lo] acts as sentinel
            }
      
            // check if pointers cross
            if (i >= j) break;
      
            exch(a, i, j);
        }
      
        // put partitioning item v at a[j]
        exch(a, lo, j);
      
        // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
        return j;
    }

  • 切分代码实现：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    // 对arr[l...r]部分进行partition操作
    // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
    //下面这个写法针对于：j 表示大于 V 的元素的索引，i 表示小于 V 元素的索引，当i 小于 V 时，将 j++，并将交换swap(arr[j], arr[i])元素。
    public int partition(T arr[], int l, int r) {
        T v = arr[l];
        //分界点
        int j = l;
        // i 是当前访问的元素
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < v) {
                swap(arr[j+1], arr[i]);
                j++;
            }
        }
        //最后切换 V 与 arr[j] 的位置，将 V 放在中间位置，左边是小于它的元素，右边是大于它的元素
        swap(arr[l], arr[j]);
        return j;
    }

  • 当数据较少时切换到插入排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // cutoff to insertion sort, must be >= 1
    private static final int INSERTION_SORT_CUTOFF = 8; 
    // quicksort the subarray from a[lo] to a[hi]
    private static void sort(Comparable[] a, int lo, int hi) { 
        if (hi <= lo) return;
        // cutoff to insertion sort (Insertion.sort() uses half-open intervals)
        int n = hi - lo + 1;
        if (n <= INSERTION_SORT_CUTOFF) {
            Insertion.sort(a, lo, hi + 1);
            return;
        }
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
    }

  • 双路快速排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public int partition(T arr, int l, int r) {
        T v = arr[l];
        // arr[l + 1 ... i] <= v; arr[j...r] >= v;
        int i = l + 1, j = r;
        while(true) {
            while(i <= r && arr[i] < v) i++;
            while(j >= l + 1 && arr[j] > v) j--;
            if (i > j) break;
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
        swap(arr[l], arr[j]);
        return j;
    }

  • 三路快速排序算法： 适用处理大量重复元素

    • 第一种方式

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      // quicksort the subarray a[lo .. hi] using 3-way partitioning
      private static void sort(Comparable[] a, int lo, int hi) { 
          if (hi <= lo) return;
          int lt = lo, gt = hi;
          Comparable v = a[lo];
          int i = lo + 1;
          while (i <= gt) {
              int cmp = a[i].compareTo(v);
              if      (cmp < 0) exch(a, lt++, i++);
              else if (cmp > 0) exch(a, i, gt--);
              else              i++;
          }
          
          // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 
          sort(a, lo, lt-1);
          sort(a, gt+1, hi);
          assert isSorted(a, lo, hi);
      }

    • 第二种方式

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      public void quickSort3Way(T arr[], int l, int r){
          T v = arr[l];
          int lt = l;// arr[l+1 ...lt]  < v
          int gt = r + 1; // arr[gt ...r] > v
          int i = l + 1; // arr[lt+1 ... i] == v
          while(i < gt) {
              if (arr[i] < v) {
                  swap(arr[i], arr[lt+1]);
                  lt++;
                  i++;
              } else if (arr[i] > v) {
                  swap(arr[i], arr[gt - 1]);
                  gt--;
              } else {
                  i++;
              }
          }
          swap(arr[l], arr[lt]);
          
          quickSort3Way(arr, l, lt - 1);
          quickSort3Way(arr, gt, r);
      }

  • 用非递归方式进行快速排序

    用 Stack 存储数组的下标

    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
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    package sort.algorithm;
    import java.util.Stack;
    //快速排序的非递归实现，利用系统的栈stack
    public class QuickSortNonRecursion {
         public static void main(String[] args) { 
             QuickSortNonRecursion qsnr = new QuickSortNonRecursion(); 
             int[] array = {0, 2, 11, 121, 18, 99, 3, 5, 101, 22, 9, 100}; 
             qsnr.quicksort(array); 
              for (int i : array) { 
                    System.out.print(i + "  "); 
              } 
            } 
                     
            public void quicksort(int[] array) { 
                if (array == null || array.length == 1) return; 
                //存放开始与结束索引
                Stack<Integer> s = new Stack<Integer>();  
                //压栈        
                s.push(0);  
                s.push(array.length - 1);  
                //利用循环里实现
                while (!s.empty()) {  
                    int right = s.pop();  
                    int left = s.pop();  
                    //如果最大索引小于等于左边索引，说明结束了
                    if (right <= left) continue;  
                             
                    int i = partition(array, left, right);  
                    if (left < i - 1) { 
                        s.push(left); 
                        s.push(i - 1); 
                    }  
                    if (i + 1 < right) { 
                        s.push(i+1); 
                        s.push(right); 
                    } 
                }  
            } 
            //找到轴心，进行交换 
            public int partition (int[] data, int first, int end)
            { 
                int temp;
                int i=first,j=end;
                if(first<end)
                {
                    temp=data[i];
                    //当i=j的时候，则说明扫描完成了
                    while(i<j)
                    {
                        //从右边向左边扫描找到一个小于temp的元素
                        while(j>i&&data[j]>temp)j--;
                        if(i<j)
                        {
                            //将该元素赋值给temp
                            data[i]=data[j];
                            //赋值后就应该将i+1指向下一个序号
                            i++;
                        }
                               
                        //然后从左边向右边开始扫描，找到一个大于temp的元素
                        while(i<j&&temp>data[i])i++;
                        if(i<j)
                        {
                            //将该元素赋值给temp
                            data[j]=data[i];
                            //赋值后就应该将j-1指向前一个序号
                            j--;
                        }
                    }
                    //将轴数据放在i位置中
                    data[i]=temp;
                }
                return i;
            } 
        }
      private static int partition(int[] a, int start, int end) {
            int pivot = a[start];
            while (start < end) {
                while (start < end && a[end] >= pivot)
                    end--;
                a[start] = a[end];
                while (start < end && a[start] <= pivot)
                    start++;
                a[end] = a[start];
            }
            a[start] = pivot;
            return start;
        }

我的理解：快速排序的思想是 选取一个基准元素，一般是第一个元素 arr[0]，从数组的左边开始向右扫描，找到第一个比 基准元素大的元素的索引 i，同时在数组的末尾从右向左扫描找到第一个比数组小的元素索引 j，交换他们的位置，如此重复，最后将基准元素与右侧指针所指向的元素arr[j]交换位置，至此我们就确定了切分元素的在数组的位置。递归处理从起始点到 j - 1的元素,和处理从j + 1 到 len （数组长度）的元素。

Heap Sort 堆排序

二叉堆： 是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级存储（不使用数组的第一个元素）。

二叉堆是一颗完全二叉树；用数组存储二叉堆。

最大堆： 堆中某一个节点的值总是不大于其父结点的值；

最大堆

  • 上浮：因为子结点变得比父结点大导致堆的有序状态被破坏，那么通过交换它和它的父结点来修复堆。

    1
    2
    3
    4
    5
    6
    private void swim(int k) {
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }

  • 下沉：将它与它的两个子结点中的较大者交换来恢复堆的有序状态；

    1
    2
    3
    4
    5
    6
    7
    8
    9
    private void sink(int k) {
        while (2*k <= n) {
            int j = 2*k;
            if (j < n && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

  • 基于堆的优先队列

    JAVA 实现：

    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
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    public class MaxPQ<Key> implements Iterable<Key> {
        private Key[] pq;                    // store items at indices 1 to n
        private int n;                       // number of items on priority queue
        private Comparator<Key> comparator;  // optional comparator
        /**
         * Initializes an empty priority queue with the given initial capacity.
         *
         * @param  initCapacity the initial capacity of this priority queue
         */
        public MaxPQ(int initCapacity) {
            pq = (Key[]) new Object[initCapacity + 1];
            n = 0;
        }
        /**
         * Initializes an empty priority queue.
         */
        public MaxPQ() {
            this(1);
        }
        /**
         * Initializes an empty priority queue with the given initial capacity,
         * using the given comparator.
         *
         * @param  initCapacity the initial capacity of this priority queue
         * @param  comparator the order in which to compare the keys
         */
        public MaxPQ(int initCapacity, Comparator<Key> comparator) {
            this.comparator = comparator;
            pq = (Key[]) new Object[initCapacity + 1];
            n = 0;
        }
        /**
         * Initializes an empty priority queue using the given comparator.
         *
         * @param  comparator the order in which to compare the keys
         */
        public MaxPQ(Comparator<Key> comparator) {
            this(1, comparator);
        }
        /**
         * Initializes a priority queue from the array of keys.
         * Takes time proportional to the number of keys, using sink-based heap construction.
         *
         * @param  keys the array of keys
         */
        public MaxPQ(Key[] keys) {
            n = keys.length;
            pq = (Key[]) new Object[keys.length + 1];
            for (int i = 0; i < n; i++)
                pq[i+1] = keys[i];
            //构造堆
            for (int k = n/2; k >= 1; k--)
                sink(k);
            assert isMaxHeap();
        }
          
        /**
         * Returns true if this priority queue is empty.
         *
         * @return {@code true} if this priority queue is empty;
         *         {@code false} otherwise
         */
        public boolean isEmpty() {
            return n == 0;
        }
        /**
         * Returns the number of keys on this priority queue.
         *
         * @return the number of keys on this priority queue
         */
        public int size() {
            return n;
        }
        /**
         * Returns a largest key on this priority queue.
         *
         * @return a largest key on this priority queue
         * @throws NoSuchElementException if this priority queue is empty
         */
        public Key max() {
            if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
            return pq[1];
        }
        // helper function to double the size of the heap array
        private void resize(int capacity) {
            assert capacity > n;
            Key[] temp = (Key[]) new Object[capacity];
            for (int i = 1; i <= n; i++) {
                temp[i] = pq[i];
            }
            pq = temp;
        }
        /**
         * Adds a new key to this priority queue.
         *
         * @param  x the new key to add to this priority queue
         */
        public void insert(Key x) {
            // double size of array if necessary
            if (n == pq.length - 1) resize(2 * pq.length);
            // add x, and percolate it up to maintain heap invariant
            pq[++n] = x;
            swim(n);
            assert isMaxHeap();
        }
        /**
         * Removes and returns a largest key on this priority queue.
         *
         * @return a largest key on this priority queue
         * @throws NoSuchElementException if this priority queue is empty
         */
        public Key delMax() {
            if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
            Key max = pq[1];
            exch(1, n--);
            sink(1);
            pq[n+1] = null;     // to avoid loiterig and help with garbage collection
            if ((n > 0) && (n == (pq.length - 1) / 4)) resize(pq.length / 2);
            assert isMaxHeap();
            return max;
        }
       /***************************************************************************
        * Helper functions to restore the heap invariant.
        ***************************************************************************/
        private void swim(int k) {
            while (k > 1 && less(k/2, k)) {
                exch(k, k/2);
                k = k/2;
            }
        }
        private void sink(int k) {
            while (2*k <= n) {
                int j = 2*k;
                if (j < n && less(j, j+1)) j++;
                if (!less(k, j)) break;
                exch(k, j);
                k = j;
            }
        }
       /***************************************************************************
        * Helper functions for compares and swaps.
        ***************************************************************************/
        private boolean less(int i, int j) {
            if (comparator == null) {
                return ((Comparable<Key>) pq[i]).compareTo(pq[j]) < 0;
            }
            else {
                return comparator.compare(pq[i], pq[j]) < 0;
            }
        }
        private void exch(int i, int j) {
            Key swap = pq[i];
            pq[i] = pq[j];
            pq[j] = swap;
        }
        // is pq[1..N] a max heap?
        private boolean isMaxHeap() {
            return isMaxHeap(1);
        }
        // is subtree of pq[1..n] rooted at k a max heap?
        private boolean isMaxHeap(int k) {
            if (k > n) return true;
            int left = 2*k;
            int right = 2*k + 1;
            if (left  <= n && less(k, left))  return false;
            if (right <= n && less(k, right)) return false;
            return isMaxHeap(left) && isMaxHeap(right);
        }
       /***************************************************************************
        * Iterator.
        ***************************************************************************/
        /**
         * Returns an iterator that iterates over the keys on this priority queue
         * in descending order.
         * The iterator doesn't implement {@code remove()} since it's optional.
         *
         * @return an iterator that iterates over the keys in descending order
         */
        public Iterator<Key> iterator() {
            return new HeapIterator();
        }
        private class HeapIterator implements Iterator<Key> {
            // create a new pq
            private MaxPQ<Key> copy;
            // add all items to copy of heap
            // takes linear time since already in heap order so no keys move
            public HeapIterator() {
                if (comparator == null) copy = new MaxPQ<Key>(size());
                else                    copy = new MaxPQ<Key>(size(), comparator);
                for (int i = 1; i <= n; i++)
                    copy.insert(pq[i]);
            }
            public boolean hasNext()  { return !copy.isEmpty();                     }
            public void remove()      { throw new UnsupportedOperationException();  }
            public Key next() {
                if (!hasNext()) throw new NoSuchElementException();
                return copy.delMax();
            }
        }
        /**
         * Unit tests the {@code MaxPQ} data type.
         *
         * @param args the command-line arguments
         */
        public static void main(String[] args) {
            MaxPQ<String> pq = new MaxPQ<String>();
            while (!StdIn.isEmpty()) {
                String item = StdIn.readString();
                if (!item.equals("-")) pq.insert(item);
                else if (!pq.isEmpty()) StdOut.print(pq.delMax() + " ");
            }
            StdOut.println("(" + pq.size() + " left on pq)");
        }
    }

堆排序

  1. 堆的构造阶段，从第一个不是叶子结点的位置开始下沉操作。

    聪明的做法：从右至左构造用 sink() 函数构造子堆，将数组中的每个位置都看成是一个子堆的根结点，那么在该结点上调用 sink() 可以将它们变成一个堆，这个过程会递归地建立起堆的秩序，开始时我们只需要扫描数组中的一半元素，因为我们可以跳过大小为1的子堆，最后在位置为1 上调用 sink() 方法，扫描结束。

  2. 下沉排序阶段 ， 从 堆中按递减顺序取出所有元素并得到排序结果；

    本质是将堆中的最大元素删除，然后放入堆缩小后数组中空出的位置。

  • 堆的构造

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public MaxPQ(Key[] keys) {
        n = keys.length;
        pq = (Key[]) new Object[keys.length + 1];
        for (int i = 0; i < n; i++)
            pq[i+1] = keys[i];
        //构造堆
        for (int k = n/2; k >= 1; k--)
            sink(k);
        assert isMaxHeap();
    }

  • 堆的下沉排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public static void sort(Comparable[] pq) {
        int n = pq.length;
        for (int k = n/2; k >= 1; k--)
            sink(pq, k, n);
        //下沉
        while (n > 1) {
            exch(pq, 1, n--);
            sink(pq, 1, n);
        }
    }

  • 堆的实现：

    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
    66
    public class Heap {
        // This class should not be instantiated.
        private Heap() { }
        /**
         * Rearranges the array in ascending order, using the natural order.
         * @param pq the array to be sorted
         */
        public static void sort(Comparable[] pq) {
            int n = pq.length;
            for (int k = n/2; k >= 1; k--)
                sink(pq, k, n);
            while (n > 1) {
                exch(pq, 1, n--);
                sink(pq, 1, n);
            }
        }
       /***************************************************************************
        * Helper functions to restore the heap invariant.
        ***************************************************************************/
        private static void sink(Comparable[] pq, int k, int n) {
            while (2*k <= n) {
                int j = 2*k;
                if (j < n && less(pq, j, j+1)) j++;
                if (!less(pq, k, j)) break;
                exch(pq, k, j);
                k = j;
            }
        }
       /***************************************************************************
        * Helper functions for comparisons and swaps.
        * Indices are "off-by-one" to support 1-based indexing.
        ***************************************************************************/
        private static boolean less(Comparable[] pq, int i, int j) {
            return pq[i-1].compareTo(pq[j-1]) < 0;
        }
        private static void exch(Object[] pq, int i, int j) {
            Object swap = pq[i-1];
            pq[i-1] = pq[j-1];
            pq[j-1] = swap;
        }
        // print array to standard output
        private static void show(Comparable[] a) {
            for (int i = 0; i < a.length; i++) {
                StdOut.println(a[i]);
            }
        }
        /**
         * Reads in a sequence of strings from standard input; heapsorts them; 
         * and prints them to standard output in ascending order. 
         *
         * @param args the command-line arguments
         */
        public static void main(String[] args) {
            String[] a = StdIn.readAllStrings();
            Heap.sort(a);
            show(a);
        }
    }

最小堆

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
public class MinPQ<Key> implements Iterable<Key> {
    private Key[] pq;                    // store items at indices 1 to n
    private int n;                       // number of items on priority queue
    private Comparator<Key> comparator;  // optional comparator
    /**
     * Initializes an empty priority queue with the given initial capacity.
     *
     * @param  initCapacity the initial capacity of this priority queue
     */
    public MinPQ(int initCapacity) {
        pq = (Key[]) new Object[initCapacity + 1];
        n = 0;
    }
    /**
     * Initializes an empty priority queue.
     */
    public MinPQ() {
        this(1);
    }
    /**
     * Initializes an empty priority queue with the given initial capacity,
     * using the given comparator.
     *
     * @param  initCapacity the initial capacity of this priority queue
     * @param  comparator the order in which to compare the keys
     */
    public MinPQ(int initCapacity, Comparator<Key> comparator) {
        this.comparator = comparator;
        pq = (Key[]) new Object[initCapacity + 1];
        n = 0;
    }
    /**
     * Initializes an empty priority queue using the given comparator.
     *
     * @param  comparator the order in which to compare the keys
     */
    public MinPQ(Comparator<Key> comparator) {
        this(1, comparator);
    }
    /**
     * Initializes a priority queue from the array of keys.
     * <p>
     * Takes time proportional to the number of keys, using sink-based heap construction.
     *
     * @param  keys the array of keys
     */
    public MinPQ(Key[] keys) {
        n = keys.length;
        pq = (Key[]) new Object[keys.length + 1];
        for (int i = 0; i < n; i++)
            pq[i+1] = keys[i];
        for (int k = n/2; k >= 1; k--)
            sink(k);
        assert isMinHeap();
    }
    /**
     * Returns true if this priority queue is empty.
     *
     * @return {@code true} if this priority queue is empty;
     *         {@code false} otherwise
     */
    public boolean isEmpty() {
        return n == 0;
    }
    /**
     * Returns the number of keys on this priority queue.
     *
     * @return the number of keys on this priority queue
     */
    public int size() {
        return n;
    }
    /**
     * Returns a smallest key on this priority queue.
     *
     * @return a smallest key on this priority queue
     * @throws NoSuchElementException if this priority queue is empty
     */
    public Key min() {
        if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        return pq[1];
    }
    // helper function to double the size of the heap array
    private void resize(int capacity) {
        assert capacity > n;
        Key[] temp = (Key[]) new Object[capacity];
        for (int i = 1; i <= n; i++) {
            temp[i] = pq[i];
        }
        pq = temp;
    }
    /**
     * Adds a new key to this priority queue.
     *
     * @param  x the key to add to this priority queue
     */
    public void insert(Key x) {
        // double size of array if necessary
        if (n == pq.length - 1) resize(2 * pq.length);
        // add x, and percolate it up to maintain heap invariant
        pq[++n] = x;
        swim(n);
        assert isMinHeap();
    }
    /**
     * Removes and returns a smallest key on this priority queue.
     *
     * @return a smallest key on this priority queue
     * @throws NoSuchElementException if this priority queue is empty
     */
    public Key delMin() {
        if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        Key min = pq[1];
        exch(1, n--);
        sink(1);
        pq[n+1] = null;     // to avoid loiterig and help with garbage collection
        if ((n > 0) && (n == (pq.length - 1) / 4)) resize(pq.length / 2);
        assert isMinHeap();
        return min;
    }
   /***************************************************************************
    * Helper functions to restore the heap invariant.
    ***************************************************************************/
    private void swim(int k) {
        while (k > 1 && greater(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
    private void sink(int k) {
        while (2*k <= n) {
            int j = 2*k;
            if (j < n && greater(j, j+1)) j++;
            if (!greater(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
   /***************************************************************************
    * Helper functions for compares and swaps.
    ***************************************************************************/
    private boolean greater(int i, int j) {
        if (comparator == null) {
            return ((Comparable<Key>) pq[i]).compareTo(pq[j]) > 0;
        }
        else {
            return comparator.compare(pq[i], pq[j]) > 0;
        }
    }
    private void exch(int i, int j) {
        Key swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
    }
    // is pq[1..N] a min heap?
    private boolean isMinHeap() {
        return isMinHeap(1);
    }
    // is subtree of pq[1..n] rooted at k a min heap?
    private boolean isMinHeap(int k) {
        if (k > n) return true;
        int left = 2*k;
        int right = 2*k + 1;
        if (left  <= n && greater(k, left))  return false;
        if (right <= n && greater(k, right)) return false;
        return isMinHeap(left) && isMinHeap(right);
    }
    /**
     * Returns an iterator that iterates over the keys on this priority queue
     * in ascending order.
     * <p>
     * The iterator doesn't implement {@code remove()} since it's optional.
     *
     * @return an iterator that iterates over the keys in ascending order
     */
    public Iterator<Key> iterator() {
        return new HeapIterator();
    }
    private class HeapIterator implements Iterator<Key> {
        // create a new pq
        private MinPQ<Key> copy;
        // add all items to copy of heap
        // takes linear time since already in heap order so no keys move
        public HeapIterator() {
            if (comparator == null) copy = new MinPQ<Key>(size());
            else                    copy = new MinPQ<Key>(size(), comparator);
            for (int i = 1; i <= n; i++)
                copy.insert(pq[i]);
        }
        public boolean hasNext()  { return !copy.isEmpty();                     }
        public void remove()      { throw new UnsupportedOperationException();  }
        public Key next() {
            if (!hasNext()) throw new NoSuchElementException();
            return copy.delMin();
        }
    }
    /**
     * Unit tests the {@code MinPQ} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        MinPQ<String> pq = new MinPQ<String>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) pq.insert(item);
            else if (!pq.isEmpty()) StdOut.print(pq.delMin() + " ");
        }
        StdOut.println("(" + pq.size() + " left on pq)");
    }
}

索引堆

最大索引堆
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
public class IndexMaxPQ<Key extends Comparable<Key>> implements Iterable<Integer> {
    private int n;           // number of elements on PQ
    private int[] pq;        // binary heap using 1-based indexing
    private int[] qp;        // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
    private Key[] keys;      // keys[i] = priority of i
    /**
     * Initializes an empty indexed priority queue with indices between {@code 0}
     * and {@code maxN - 1}.
     *
     * @param  maxN the keys on this priority queue are index from {@code 0} to {@code maxN - 1}
     * @throws IllegalArgumentException if {@code maxN < 0}
     */
    public IndexMaxPQ(int maxN) {
        if (maxN < 0) throw new IllegalArgumentException();
        n = 0;
        keys = (Key[]) new Comparable[maxN + 1];    // make this of length maxN??
        pq   = new int[maxN + 1];
        qp   = new int[maxN + 1];                   // make this of length maxN??
        for (int i = 0; i <= maxN; i++)
            qp[i] = -1;
    }
    /**
     * Returns true if this priority queue is empty.
     *
     * @return {@code true} if this priority queue is empty;
     *         {@code false} otherwise
     */
    public boolean isEmpty() {
        return n == 0;
    }
    /**
     * Is {@code i} an index on this priority queue?
     *
     * @param  i an index
     * @return {@code true} if {@code i} is an index on this priority queue;
     *         {@code false} otherwise
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     */
    public boolean contains(int i) {
        return qp[i] != -1;
    }
    /**
     * Returns the number of keys on this priority queue.
     *
     * @return the number of keys on this priority queue 
     */
    public int size() {
        return n;
    }
   /**
     * Associate key with index i.
     *
     * @param  i an index
     * @param  key the key to associate with index {@code i}
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws IllegalArgumentException if there already is an item
     *         associated with index {@code i}
     */
    public void insert(int i, Key key) {
        if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
        n++;
        qp[i] = n;
        pq[n] = i;
        keys[i] = key;
        swim(n);
    }
    /**
     * Returns an index associated with a maximum key.
     *
     * @return an index associated with a maximum key
     * @throws NoSuchElementException if this priority queue is empty
     */
    public int maxIndex() {
        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
        return pq[1];
    }
    /**
     * Returns a maximum key.
     *
     * @return a maximum key
     * @throws NoSuchElementException if this priority queue is empty
     */
    public Key maxKey() {
        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
        return keys[pq[1]];
    }
    /**
     * Removes a maximum key and returns its associated index.
     *
     * @return an index associated with a maximum key
     * @throws NoSuchElementException if this priority queue is empty
     */
    public int delMax() {
        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
        int min = pq[1];
        exch(1, n--);
        sink(1);
        assert pq[n+1] == min;
        qp[min] = -1;        // delete
        keys[min] = null;    // to help with garbage collection
        pq[n+1] = -1;        // not needed
        return min;
    }
    /**
     * Returns the key associated with index {@code i}.
     *
     * @param  i the index of the key to return
     * @return the key associated with index {@code i}
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws NoSuchElementException no key is associated with index {@code i}
     */
    public Key keyOf(int i) {
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        else return keys[i];
    }
    /**
     * Change the key associated with index {@code i} to the specified value.
     *
     * @param  i the index of the key to change
     * @param  key change the key associated with index {@code i} to this key
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     */
    public void changeKey(int i, Key key) {
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        keys[i] = key;
        swim(qp[i]);
        sink(qp[i]);
    }
   /**
     * Change the key associated with index {@code i} to the specified value.
     *
     * @param  i the index of the key to change
     * @param  key change the key associated with index {@code i} to this key
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @deprecated Replaced by {@code changeKey(int, Key)}.
     */
    @Deprecated
    public void change(int i, Key key) {
        changeKey(i, key);
    }
    /**
     * Increase the key associated with index {@code i} to the specified value.
     *
     * @param  i the index of the key to increase
     * @param  key increase the key associated with index {@code i} to this key
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws IllegalArgumentException if {@code key <= keyOf(i)}
     * @throws NoSuchElementException no key is associated with index {@code i}
     */
    public void increaseKey(int i, Key key) {
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if (keys[i].compareTo(key) >= 0)
            throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key");
        keys[i] = key;
        swim(qp[i]);
    }
    /**
     * Decrease the key associated with index {@code i} to the specified value.
     *
     * @param  i the index of the key to decrease
     * @param  key decrease the key associated with index {@code i} to this key
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws IllegalArgumentException if {@code key >= keyOf(i)}
     * @throws NoSuchElementException no key is associated with index {@code i}
     */
    public void decreaseKey(int i, Key key) {
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if (keys[i].compareTo(key) <= 0)
            throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key");
        keys[i] = key;
        sink(qp[i]);
    }
    /**
     * Remove the key on the priority queue associated with index {@code i}.
     *
     * @param  i the index of the key to remove
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws NoSuchElementException no key is associated with index {@code i}
     */
    public void delete(int i) {
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        int index = qp[i];
        exch(index, n--);
        swim(index);
        sink(index);
        keys[i] = null;
        qp[i] = -1;
    }
   /***************************************************************************
    * General helper functions.
    ***************************************************************************/
    private boolean less(int i, int j) {
        return keys[pq[i]].compareTo(keys[pq[j]]) < 0;
    }
    private void exch(int i, int j) {
        int swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }
   /***************************************************************************
    * Heap helper functions.
    ***************************************************************************/
    private void swim(int k) {
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
    private void sink(int k) {
        while (2*k <= n) {
            int j = 2*k;
            if (j < n && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
    /**
     * Returns an iterator that iterates over the keys on the
     * priority queue in descending order.
     * The iterator doesn't implement {@code remove()} since it's optional.
     *
     * @return an iterator that iterates over the keys in descending order
     */
    public Iterator<Integer> iterator() {
        return new HeapIterator();
    }
    private class HeapIterator implements Iterator<Integer> {
        // create a new pq
        private IndexMaxPQ<Key> copy;
        // add all elements to copy of heap
        // takes linear time since already in heap order so no keys move
        public HeapIterator() {
            copy = new IndexMaxPQ<Key>(pq.length - 1);
            for (int i = 1; i <= n; i++)
                copy.insert(pq[i], keys[pq[i]]);
        }
        public boolean hasNext()  { return !copy.isEmpty();                     }
        public void remove()      { throw new UnsupportedOperationException();  }
        public Integer next() {
            if (!hasNext()) throw new NoSuchElementException();
            return copy.delMax();
        }
    }
    /**
     * Unit tests the {@code IndexMaxPQ} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        // insert a bunch of strings
        String[] strings = { "it", "was", "the", "best", "of", "times", "it", "was", "the", "worst" };
        IndexMaxPQ<String> pq = new IndexMaxPQ<String>(strings.length);
        for (int i = 0; i < strings.length; i++) {
            pq.insert(i, strings[i]);
        }
        // print each key using the iterator
        for (int i : pq) {
            StdOut.println(i + " " + strings[i]);
        }
        StdOut.println();
        // increase or decrease the key
        for (int i = 0; i < strings.length; i++) {
            if (StdRandom.uniform() < 0.5)
                pq.increaseKey(i, strings[i] + strings[i]);
            else
                pq.decreaseKey(i, strings[i].substring(0, 1));
        }
        // delete and print each key
        while (!pq.isEmpty()) {
            String key = pq.maxKey();
            int i = pq.delMax();
            StdOut.println(i + " " + key);
        }
        StdOut.println();
        // reinsert the same strings
        for (int i = 0; i < strings.length; i++) {
            pq.insert(i, strings[i]);
        }
        // delete them in random order
        int[] perm = new int[strings.length];
        for (int i = 0; i < strings.length; i++)
            perm[i] = i;
        StdRandom.shuffle(perm);
        for (int i = 0; i < perm.length; i++) {
            String key = pq.keyOf(perm[i]);
            pq.delete(perm[i]);
            StdOut.println(perm[i] + " " + key);
        }
    }
}
最小索引堆
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
public class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer> {
    private int maxN;        // maximum number of elements on PQ
    private int n;           // number of elements on PQ
    private int[] pq;        // binary heap using 1-based indexing
    private int[] qp;        // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
    private Key[] keys;      // keys[i] = priority of i
    /**
     * Initializes an empty indexed priority queue with indices between {@code 0}
     * and {@code maxN - 1}.
     * @param  maxN the keys on this priority queue are index from {@code 0}
     *         {@code maxN - 1}
     * @throws IllegalArgumentException if {@code maxN < 0}
     */
    public IndexMinPQ(int maxN) {
        if (maxN < 0) throw new IllegalArgumentException();
        this.maxN = maxN;
        n = 0;
        keys = (Key[]) new Comparable[maxN + 1];    // make this of length maxN??
        pq   = new int[maxN + 1];
        qp   = new int[maxN + 1];                   // make this of length maxN??
        for (int i = 0; i <= maxN; i++)
            qp[i] = -1;
    }
    /**
     * Returns true if this priority queue is empty.
     *
     * @return {@code true} if this priority queue is empty;
     *         {@code false} otherwise
     */
    public boolean isEmpty() {
        return n == 0;
    }
    /**
     * Is {@code i} an index on this priority queue?
     *
     * @param  i an index
     * @return {@code true} if {@code i} is an index on this priority queue;
     *         {@code false} otherwise
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     */
    public boolean contains(int i) {
        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
        return qp[i] != -1;
    }
    /**
     * Returns the number of keys on this priority queue.
     *
     * @return the number of keys on this priority queue
     */
    public int size() {
        return n;
    }
    /**
     * Associates key with index {@code i}.
     *
     * @param  i an index
     * @param  key the key to associate with index {@code i}
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws IllegalArgumentException if there already is an item associated
     *         with index {@code i}
     */
    public void insert(int i, Key key) {
        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
        if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
        n++;
        qp[i] = n;
        pq[n] = i;
        keys[i] = key;
        swim(n);
    }
    /**
     * Returns an index associated with a minimum key.
     *
     * @return an index associated with a minimum key
     * @throws NoSuchElementException if this priority queue is empty
     */
    public int minIndex() {
        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
        return pq[1];
    }
    /**
     * Returns a minimum key.
     *
     * @return a minimum key
     * @throws NoSuchElementException if this priority queue is empty
     */
    public Key minKey() {
        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
        return keys[pq[1]];
    }
    /**
     * Removes a minimum key and returns its associated index.
     * @return an index associated with a minimum key
     * @throws NoSuchElementException if this priority queue is empty
     */
    public int delMin() {
        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
        int min = pq[1];
        exch(1, n--);
        sink(1);
        assert min == pq[n+1];
        qp[min] = -1;        // delete
        keys[min] = null;    // to help with garbage collection
        pq[n+1] = -1;        // not needed
        return min;
    }
    /**
     * Returns the key associated with index {@code i}.
     *
     * @param  i the index of the key to return
     * @return the key associated with index {@code i}
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws NoSuchElementException no key is associated with index {@code i}
     */
    public Key keyOf(int i) {
        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        else return keys[i];
    }
    /**
     * Change the key associated with index {@code i} to the specified value.
     *
     * @param  i the index of the key to change
     * @param  key change the key associated with index {@code i} to this key
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws NoSuchElementException no key is associated with index {@code i}
     */
    public void changeKey(int i, Key key) {
        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        keys[i] = key;
        swim(qp[i]);
        sink(qp[i]);
    }
    /**
     * Change the key associated with index {@code i} to the specified value.
     *
     * @param  i the index of the key to change
     * @param  key change the key associated with index {@code i} to this key
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @deprecated Replaced by {@code changeKey(int, Key)}.
     */
    @Deprecated
    public void change(int i, Key key) {
        changeKey(i, key);
    }
    /**
     * Decrease the key associated with index {@code i} to the specified value.
     *
     * @param  i the index of the key to decrease
     * @param  key decrease the key associated with index {@code i} to this key
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws IllegalArgumentException if {@code key >= keyOf(i)}
     * @throws NoSuchElementException no key is associated with index {@code i}
     */
    public void decreaseKey(int i, Key key) {
        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if (keys[i].compareTo(key) <= 0)
            throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key");
        keys[i] = key;
        swim(qp[i]);
    }
    /**
     * Increase the key associated with index {@code i} to the specified value.
     *
     * @param  i the index of the key to increase
     * @param  key increase the key associated with index {@code i} to this key
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws IllegalArgumentException if {@code key <= keyOf(i)}
     * @throws NoSuchElementException no key is associated with index {@code i}
     */
    public void increaseKey(int i, Key key) {
        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if (keys[i].compareTo(key) >= 0)
            throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key");
        keys[i] = key;
        sink(qp[i]);
    }
    /**
     * Remove the key associated with index {@code i}.
     *
     * @param  i the index of the key to remove
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws NoSuchElementException no key is associated with index {@code i}
     */
    public void delete(int i) {
        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        int index = qp[i];
        exch(index, n--);
        swim(index);
        sink(index);
        keys[i] = null;
        qp[i] = -1;
    }
   /***************************************************************************
    * General helper functions.
    ***************************************************************************/
    private boolean greater(int i, int j) {
        return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
    }
    private void exch(int i, int j) {
        int swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }
   /***************************************************************************
    * Heap helper functions.
    ***************************************************************************/
    private void swim(int k) {
        while (k > 1 && greater(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
    private void sink(int k) {
        while (2*k <= n) {
            int j = 2*k;
            if (j < n && greater(j, j+1)) j++;
            if (!greater(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
   /***************************************************************************
    * Iterators.
    ***************************************************************************/
    /**
     * Returns an iterator that iterates over the keys on the
     * priority queue in ascending order.
     * The iterator doesn't implement {@code remove()} since it's optional.
     *
     * @return an iterator that iterates over the keys in ascending order
     */
    public Iterator<Integer> iterator() { return new HeapIterator(); }
    private class HeapIterator implements Iterator<Integer> {
        // create a new pq
        private IndexMinPQ<Key> copy;
        // add all elements to copy of heap
        // takes linear time since already in heap order so no keys move
        public HeapIterator() {
            copy = new IndexMinPQ<Key>(pq.length - 1);
            for (int i = 1; i <= n; i++)
                copy.insert(pq[i], keys[pq[i]]);
        }
        public boolean hasNext()  { return !copy.isEmpty();                     }
        public void remove()      { throw new UnsupportedOperationException();  }
        public Integer next() {
            if (!hasNext()) throw new NoSuchElementException();
            return copy.delMin();
        }
    }
    /**
     * Unit tests the {@code IndexMinPQ} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        // insert a bunch of strings
        String[] strings = { "it", "was", "the", "best", "of", "times", "it", "was", "the", "worst" };
        IndexMinPQ<String> pq = new IndexMinPQ<String>(strings.length);
        for (int i = 0; i < strings.length; i++) {
            pq.insert(i, strings[i]);
        }
        // delete and print each key
        while (!pq.isEmpty()) {
            int i = pq.delMin();
            StdOut.println(i + " " + strings[i]);
        }
        StdOut.println();
        // reinsert the same strings
        for (int i = 0; i < strings.length; i++) {
            pq.insert(i, strings[i]);
        }
        // print each key using the iterator
        for (int i : pq) {
            StdOut.println(i + " " + strings[i]);
        }
        while (!pq.isEmpty()) {
            pq.delMin();
        }
    }
}

分治算法

Merge Sort & Quick Sort

逆序对

取数组中第N大的元素

时间复杂度 O(N)

具体题目

题目：请实现一个排序算法，要求时间效率为O(n).(允许使用常量大小的辅助空间不得超过O（n）)

img

该题来自于剑指offer，用空间来换时间效率

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
package cn.stack.queue;  
//该方法用长度为100的整数数组作为辅助空间换来了O（N）的时间效率  
public class Demo3 {  
    public void sortAge(int[] ages) {  
        int length = ages.length;  
        int oldestAge = 99;  
        // 建立一个数组，用来存储每个年龄员工的数量  
        int[] timesOfAge = new int[oldestAge + 1];  
        // 初始化  
        for (int i = 0; i <= 99; i++) {  
            timesOfAge[i] = 0;  
        }  
        // 循环统计  
        int age = 0;  
        for (int i = 0; i < length; i++) {  
            age = ages[i];  
            if (age > 99 || age < 0) {  
                System.out.println("年龄输入有误");  
                return;  
            }  
            timesOfAge[age]++;  
        }  
        //进行排序，结果存储在ages数组中  
        int index = 0;  
        for (int i = 0; i <= oldestAge; i++) {  
            for (int j = 0; j < timesOfAge[i]; j++) {  
                ages[index] = i;  
                ++index;  
            }  
        }  
    }  
}