标签：增量 ret ros false argument quicksort version when imp
一、选择排序
选择排序是一种非常简单而且很直观的排序算法，此排序算法的时间复杂度为O(n2)，因此，从时间复杂度来看，需要排序的数据规模越小，效果就越好；它的好处就是在进行排序的过程中不会占用额外的内存空间。
选择排序的基本思想：每一次在n-i+1(i=1,2,3,...,n-1)个记录中选取最小的关键字作为有序序列中的第i个记录，引用《算法》第四版中的java实现代码，如下：
1 package sort;
2
3 import edu.princeton.cs.algs4.StdIn;
4 import edu.princeton.cs.algs4.StdOut;
5
6 import java.util.Comparator;
7
8 /**
9 * The {@code Selection} class provides static methods for sorting an
10 * array using selection sort.
11 * This implementation makes ~ ½ n2 compares to sort
12 * any array of length n, so it is not suitable for sorting large arrays.
13 * It performs exactly n exchanges.
14 *
15 * This sorting algorithm is not stable. It uses Θ(1) extra memory
16 * (not including the input array).
17 *
18 * For additional documentation, see
19 * Section 2.1
20 * of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
21 *
22 * @author Robert Sedgewick
23 * @author Kevin Wayne
24 */
25 public class Selection {
26
27 // This class should not be instantiated.
28 private Selection() { }
29
30 /**
31 * Rearranges the array in ascending order, using the natural order.
32 * @param a the array to be sorted
33 */
34 public static void sort(Comparable[] a) {
35 int n = a.length;
36 for (int i = 0; i ) {
37 int min = i;
38 for (int j = i+1; j ) {
39 if (less(a[j], a[min])) min = j;
40 }
41 exch(a, i, min);
42 assert isSorted(a, 0, i);
43 }
44 assert isSorted(a);
45 }
46
47 /**
48 * Rearranges the array in ascending order, using a comparator.
49 * @param a the array
50 * @param comparator the comparator specifying the order
51 */
52 public static void sort(Object[] a, Comparator comparator) {
53 int n = a.length;
54 for (int i = 0; i ) {
55 int min = i;
56 for (int j = i+1; j ) {
57 if (less(comparator, a[j], a[min])) min = j;
58 }
59 exch(a, i, min);
60 assert isSorted(a, comparator, 0, i);
61 }
62 assert isSorted(a, comparator);
63 }
64
65
66 /***************************************************************************
67 * Helper sorting functions.
68 ***************************************************************************/
69
70 // is v
71 private static boolean less(Comparable v, Comparable w) {
72 return v.compareTo(w) ;
73 }
74
75 // is v
76 private static boolean less(Comparator comparator, Object v, Object w) {
77 return comparator.compare(v, w) ;
78 }
79
80
81 // exchange a[i] and a[j]
82 private static void exch(Object[] a, int i, int j) {
83 Object swap = a[i];
84 a[i] = a[j];
85 a[j] = swap;
86 }
87
88
89 /***************************************************************************
90 * Check if array is sorted - useful for debugging.
91 ***************************************************************************/
92
93 // is the array a[] sorted?
94 private static boolean isSorted(Comparable[] a) {
95 return isSorted(a, 0, a.length - 1);
96 }
97
98 // is the array sorted from a[lo] to a[hi]
99 private static boolean isSorted(Comparable[] a, int lo, int hi) {
100 for (int i = lo + 1; i )
101 if (less(a[i], a[i-1])) return false;
102 return true;
103 }
104
105 // is the array a[] sorted?
106 private static boolean isSorted(Object[] a, Comparator comparator) {
107 return isSorted(a, comparator, 0, a.length - 1);
108 }
109
110 // is the array sorted from a[lo] to a[hi]
111 private static boolean isSorted(Object[] a, Comparator comparator, int lo, int hi) {
112 for (int i = lo + 1; i )
113 if (less(comparator, a[i], a[i-1])) return false;
114 return true;
115 }
116
117
118
119 // print array to standard output
120 private static void show(Comparable[] a) {
121 for (int i = 0; i ) {
122 StdOut.println(a[i]);
123 }
124 }
125
126 /**
127 * Reads in a sequence of strings from standard input; selection sorts them;
128 * and prints them to standard output in ascending order.
129 *
130 * @param args the command-line arguments
131 */
132 public static void main(String[] args) {
133 String[] a = StdIn.readAllStrings();
134 Selection.sort(a);
135 show(a);
136 }
137 }
Selection
二、插入排序
在插入排序中，直接插入排序是最为简单的一种排序方法，而且这种算法容易实现；此排序算法的时间复杂度为O(n2)，当待排序记录的数量n很小的时候，这是一种很好的排序方法，但是当数据规模较大的时候，就不宜采用直接插入排序，直接插入排序的基本思想：将一个记录插入到已排好序的有序表中从而得到一个新的而且记录数增加1的有序表
在直接插入排序的基础上，从减少“比较”和“移动”这两种操作的次数出发，可以优化出折半插入排序，折半插入排序所需的附加存储空间和直接插入排序相同，折半插入排序仅减少了关键字之间的比较次数，但是记录的移动次数没有发生变化。所以折半插入排序算法的时间复杂的仍然为O(n2)。除了优化出的折半插入排序，还有2-路插入排序，它是在折半插入排序的基础上再次优化得到的，它减少了过程中记录移动的次数。但是就需要为n个记录分配辅助空间。
引用《算法》第四版中的java实现代码，如下：
import java.util.Comparator;
/**
* The {@code Insertion} class provides static methods for sorting an
* array using insertion sort.
*
* In the worst case, this implementation makes ~ ½ n2
* compares and ~ ½ n2 exchanges to sort an array
* of length n. So, it is not suitable for sorting large arbitrary
* arrays. More precisely, the number of exchanges is exactly equal to the
* number of inversions. So, for example, it sorts a partially-sorted array
* in linear time.
*
* This sorting algorithm is stable.
* It uses Θ(1) extra memory (not including the input array).
*
* See InsertionPedantic.java
* for a version that eliminates the compiler warning.
*
* For additional documentation, see Section 2.1 of
* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
*
*
@author Robert Sedgewick
* @author Kevin Wayne
*/
public class Insertion {
// This class should not be instantiated.
private Insertion() { }
/**
* 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 ) {
for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
exch(a, j, j-1);
}
assert isSorted(a, 0, i);
}
assert isSorted(a);
}
/**
* Rearranges the subarray a[lo..hi) in ascending order, using the natural order.
* @param a the array to be sorted
* @param lo left endpoint (inclusive)
* @param hi right endpoint (exclusive)
*/
public static void sort(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i ) {
for (int j = i; j > lo && less(a[j], a[j-1]); j--) {
exch(a, j, j-1);
}
}
assert isSorted(a, lo, hi);
}
/**
* Rearranges the array in ascending order, using a comparator.
* @param a the array
* @param comparator the comparator specifying the order
*/
public static void sort(Object[] a, Comparator comparator) {
int n = a.length;
for (int i = 1; i ) {
for (int j = i; j > 0 && less(a[j], a[j-1], comparator); j--) {
exch(a, j, j-1);
}
assert isSorted(a, 0, i, comparator);
}
assert isSorted(a, comparator);
}
/**
* Rearranges the subarray a[lo..hi) in ascending order, using a comparator.
* @param a the array
* @param lo left endpoint (inclusive)
* @param hi right endpoint (exclusive)
* @param comparator the comparator specifying the order
*/
public static void sort(Object[] a, int lo, int hi, Comparator comparator) {
for (int i = lo + 1; i ) {
for (int j = i; j > lo && less(a[j], a[j-1], comparator); j--) {
exch(a, j, j-1);
}
}
assert isSorted(a, lo, hi, comparator);
}
// return a permutation that gives the elements in a[] in ascending order
// do not change the original array a[]
/**
* Returns a permutation that gives the elements in the array in ascending order.
* @param a the array
* @return a permutation {@code p[]} such that {@code a[p[0]]}, {@code a[p[1]]},
* ..., {@code a[p[n-1]]} are in ascending order
*/
public static int[] indexSort(Comparable[] a) {
int n = a.length;
int[] index = new int[n];
for (int i = 0; i )
index[i] = i;
for (int i = 1; i )
for (int j = i; j > 0 && less(a[index[j]], a[index[j-1]]); j--)
exch(index, j, j-1);
return index;
}
/***************************************************************************
* Helper sorting functions.
***************************************************************************/
// is v
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) ;
}
// is v
private static boolean less(Object v, Object w, Comparator comparator) {
return comparator.compare(v, w) ;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
// exchange a[i] and a[j] (for indirect sort)
private static void exch(int[] a, int i, int j) {
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}
/***************************************************************************
* Check if array is sorted - useful for debugging.
***************************************************************************/
private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length);
}
// is the array a[lo..hi) sorted
private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i )
if (less(a[i], a[i-1])) return false;
return true;
}
private static boolean isSorted(Object[] a, Comparator comparator) {
return isSorted(a, 0, a.length, comparator);
}
// is the array a[lo..hi) sorted
private static boolean isSorted(Object[] a, int lo, int hi, Comparator comparator) {
for (int i = lo + 1; i )
if (less(a[i], a[i-1], comparator)) return false;
return true;
}
// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i ) {
StdOut.println(a[i]);
}
}
/**
* Reads in a sequence of strings from standard input; insertion sorts 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();
Insertion.sort(a);
show(a);
}
}
Insert
希尔排序，又叫做“缩小增量排序”，属于插入排序的类的排序方法，在时间效率上较之前面的排序方法有较大的的改进，其算法时间复杂度为O(n2)。
希尔排序的基本思想：先将整个待排记录序列分割成为若干个子序列，分别对这若干个子序列进行插入排序，当整个序列变得基本有序的时候，在对整个序列进行一次直接插入排序。希尔排序的一个特点是：子序列并不是对整个原序列简单的“逐段分割”，而是将相隔某个“增量”的两个记录组成一个子序列，对子序列中的两个记录进行比较，然后排序，之后不断缩小增量，从而对整个序列进行排序操作。
引用《算法》第四版中的java实现代码，如下：
/**
* The {@code Shell} class provides static methods for sorting an
* array using Shellsort with
* Knuth‘s increment sequence
* (1, 4, 13, 40, ...). In the worst case, this implementation makes
* Θ(n3/2) compares and exchanges to sort
* an array of length n.
*
* This sorting algorithm is not stable.
* It uses Θ(1) extra memory (not including the input array).
*
* For additional documentation, see
* Section 2.1 of
* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
*
*
@author Robert Sedgewick
* @author Kevin Wayne
*/
public class Shell {
// This class should not be instantiated.
private Shell() { }
/**
* 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 ;
while (h >= 1) {
// h-sort the array
for (int i = h; i ) {
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);
}
/***************************************************************************
* Helper sorting functions.
***************************************************************************/
// is v
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) ;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
/***************************************************************************
* Check if array is sorted - useful for debugging.
***************************************************************************/
private static boolean isSorted(Comparable[] a) {
for (int i = 1; i )
if (less(a[i], a[i-1])) return false;
return true;
}
// is the array h-sorted?
private static boolean isHsorted(Comparable[] a, int h) {
for (int i = h; i )
if (less(a[i], a[i-h])) return false;
return true;
}
// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i ) {
StdOut.println(a[i]);
}
}
/**
* Reads in a sequence of strings from standard input; Shellsorts 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();
Shell.sort(a);
show(a);
}
}
Shell
三、冒泡排序
依次比较相邻的记录，将小记录放在前，大记录放在后；即第一趟先比较第1个和第2个数，大记录在后，小记录在前，再比较第2个记录与第3个记录，大记录在后，小记录在前，以此类推则将最大的记录移动到最后一个位置；第二趟则将次大的记录移动到倒数第二个位置......第n-1(n为无序数列的个数)趟即能完成排序。
java算法实现：
import java.io.IOException;
public class Bubble{
public static void main(String []args) {
//冒泡排序
int[] a = new int[] {1,5,8,2,3,9,4};
int i ,j;
for (i = 0; i ) {
for (j = 0; j ) {
if (a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
for (i = 0; i ) {
System.out.print(a[i]+ " ");
}
}
}
Bubble
四、快速排序
快速排序是对冒泡排序的一种改进，它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
引用《算法》第四版中的java实现代码，如下：
/**
* The {@code Quick} class provides static methods for sorting an
* array and selecting the ith smallest element in an array using quicksort.
*
* For additional documentation, see
* Section 2.3
* of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
*
*
@author Robert Sedgewick
* @author Kevin Wayne
*/
public class Quick {
// This class should not be instantiated.
private Quick() { }
/**
* 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 return;
int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
assert isSorted(a, lo, hi);
}
// partition the subarray a[lo..hi] so that a[lo..j-1] // 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]
return j;
}
/**
* Rearranges the array so that {@code a[k]} contains the kth smallest key;
* {@code a[0]} through {@code a[k-1]} are less than (or equal to) {@code a[k]}; and
* {@code a[k+1]} through {@code a[n-1]} are greater than (or equal to) {@code a[k]}.
*
* @param a the array
* @param k the rank of the key
* @return the key of rank {@code k}
* @throws IllegalArgumentException unless {@code 0 */
public static Comparable select(Comparable[] a, int k) {
if (k = a.length) {
throw new IllegalArgumentException("index is not between 0 and " + a.length + ": " + k);
}
StdRandom.shuffle(a);
int lo = 0, hi = a.length - 1;
while (hi > lo) {
int i = partition(a, lo, hi);
if (i > k) hi = i - 1;
else if (i ;
else return a[i];
}
return a[lo];
}
/***************************************************************************
* Helper sorting functions.
***************************************************************************/
// is v
private static boolean less(Comparable v, Comparable w) {
if (v == w) return false; // optimization when reference equals
return v.compareTo(w) ;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
/***************************************************************************
* Check if array is sorted - useful for debugging.
***************************************************************************/
private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length - 1);
}
private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i )
if (less(a[i], a[i-1])) return false;
return true;
}
// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i ) {
StdOut.println(a[i]);
}
}
/**
* Reads in a sequence of strings from standard input; quicksorts them;
* and prints them to standard output in ascending order.
* Shuffles the array and then prints the strings again to
* standard output, but this time, using the select method.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
String[] a = StdIn.readAllStrings();
Quick.sort(a);
show(a);
assert isSorted(a);
// shuffle
StdRandom.shuffle(a);
// display results again using select
StdOut.println();
for (int i = 0; i ) {
String ith = (String) Quick.select(a, i);
StdOut.println(ith);
}
}
}
Quick
几种排序算法学习总结
标签：增量 ret ros false argument quicksort version when imp
原文地址：https://www.cnblogs.com/jjrona/p/14551743.html