插入排序:直接插入排序
思想:将数据分为两组,一组为已排序序列,另一组为待排序序列,不断的将待排序序列加入已排序序列。最终得到的是已排序序列。
public class InsertionSort implements Sort{ public void sort(int a[]){ for(int i = 1; i < a.length; i++){ int t = a[i], j = i-1; while(j >= 0 && a[j] > t){ a[j+1] = a[j]; j--; } a[j+1] = t; } SortUtils.print(a); } public static void main(String[] args) { new InsertionSort().sort(SortUtils.generate(10)); } }插入排序:Shell排序
思想:带有间隔的插入排序,插入排序每次的消耗都在比较当前元素在已排序元素中的位置,所以希尔排序要减少这种比较,它使用带有间隔的插入排序方式,每次选取n/2作为间隔,然后跳着比较数据,直到间隔为1结束。
public class ShellSort implements Sort{ public static void shellNSort(int a[], int k) { for (int t = 0; t < k; t++) { for (int i = t + k; i < a.length; i += k) { int p = a[i], j = i - k; while (j >= 0 && p < a[j]) { a[j + k] = a[j]; j -= k; } a[j + k] = p; } } } public void sort(int a[]) { int k = a.length / 2; while (k >= 1) { shellNSort(a, k); k /= 2; } SortUtils.print(a); } public static void main(String[] args) { new ShellSort().sort(new int[] { 49, 38, 65, 97, 76, 13, 27, 48, 55, 4 }); } }选择排序:直接选择排序
思想:每次选择最大或者最小的元素,直到数据结尾,之后再交换最大元素和末尾元素,这之后按照同样的方法找到次小元素,直到只剩下一个元素为止。
public class SelectionSort implements Sort{ public void sort(int a[]){ for(int i = 1; i < a.length;i++){ int max = 0; for(int j = 1; j <= a.length-i;j++){ if(a[j] > a[max]){ max = j; } } SortUtils.swap(a, max, a.length-i); //SortUtils.print(a); } SortUtils.print(a); } public static void main(String[] args) { new SelectionSort().sort(SortUtils.generate(4091,10)); } }
思想:构建堆数据结构,每次从堆中选出堆顶元素放到堆的末尾,这样当所有的堆顶元素都被放到末尾过一次,整体就是有序的。此外如果是大顶堆,则会是从小到大的顺序,如果是小顶堆,则会是从大到小的顺序。
public class HeapSort implements Sort{ private static int left(int i) { return 2 * i + 1; } private static int right(int i) { return 2 * i + 2; } public static void maxHeapIFY(int a[], int size, int index) { int l = left(index), r = right(index); int largest = index; if (l < size && a[l] > a[index]) { largest = l; } if (r < size && a[r] > a[largest]) { largest = r; } if (largest != index) { SortUtils.swap(a, index, largest); maxHeapIFY(a, size, largest); } } public static void buildMaxHeap(int a[]) { for (int i = a.length / 2; i >= 0; i--) { maxHeapIFY(a, a.length, i); } } public void sort(int a[]) { buildMaxHeap(a); for (int i = a.length - 1; i > 0; i--) { SortUtils.swap(a, 0, i); maxHeapIFY(a, i, 0); } SortUtils.print(a); } public static void main(String[] args) { new HeapSort().sort(new int[] { 9, 9, 7, 6, 5, 4, 3, 2, 1 }); } }
思想:每次比较相邻的元素,如果第一个元素比第二个大,那么交换它们的顺序,依次如此,直到末尾,下一次对从头到倒数第二个元素做这些操作,直到最后只剩下一个元素为止。
public class BubbleSort implements Sort { public void sort(int a[]) { for (int i = a.length - 1; i > 0; i--) { boolean flag = false; for (int j = 0; j < i; j++) { if (a[j] > a[j + 1]) { SortUtils.swap(a, j, j + 1); flag = true; } } if (!flag) { break; } } SortUtils.print(a); } public static void main(String[] args) { new BubbleSort().sort(new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1 }); } }
思想:从数据中选出一个元素,每次找到这个元素应该在的位置,使得这个元素左边都比它小,右边都比它大,然后将数据分两组,这个元素左边一组,右边一组,按照这个方式,每次都能找到一个元素应该在的位置,最终所有元素就在自己的位置了。
public class QuickSort implements Sort{ public static int partition(int a[], int low, int high) { int p = a[low]; while (low < high) { while (low < high && a[high] >= p) high--; a[low] = a[high]; while (low < high && a[low] <= p) low++; a[high] = a[low]; } a[low] = p; return low; } public static void quicksort(int a[], int low, int high) { if (low < high) { int p = partition(a, low, high); quicksort(a, low, p - 1); quicksort(a, p + 1, high); } } public void sort(int a[]) { quicksort(a, 0, a.length - 1); SortUtils.print(a); } public static void main(String[] args) { new QuickSort().sort(new int[] { 4, 1, 2, 3, 5, 7, 8, 5, 9 }); } }
归并排序
思想:每次将数据分为两部分,左边一部分右边一部分,分别做归并排序,然后将两部分合并起来,递归的做这个操作,最终整个数组就是已排序序列。public class MergeSort implements Sort{ public static void merge(int a[], int low, int p, int high){ int lenC = p-low+1; int lenD = high-p; int c[] = new int[lenC+1]; int d[] = new int[lenD+1]; for(int i = 0; i < lenC;i++){ c[i] = a[low + i]; } for(int i = 0; i < lenD;i++){ d[i] = a[p + 1 + i]; } c[lenC] = d[lenD] = Integer.MAX_VALUE; int indexC = 0, indexD = 0; for(int i = low; i <= high; i++){ if(c[indexC] < d[indexD]){ a[i] = c[indexC++]; } else { a[i] = d[indexD++]; } } } public static void mergesort(int a[], int low, int high){ if(low < high){ int mid = (low + high) / 2; mergesort(a, low, mid); mergesort(a, mid+1, high); merge(a, low, mid, high); } } public void sort(int a[]){ mergesort(a, 0, a.length-1); SortUtils.print(a); } public static void main(String[] args) { new MergeSort().sort(new int[]{4,3,2,1,9,8,7,6,5}); } }
思想:按照每个位的数据大小排序,如个位,按照大小排序,按十位的大小排序,按百位的大小排序(注意必须使用稳定的排序算法,也就是说排序过程中元素的相对顺序不变),这样排序后,从头到尾取出所有的元素即排序好的序列。
public class RadixSort implements Sort{ public static class Entry { int value; Entry next; Entry pre; public Entry(int value) { this(value, null, null); } public Entry(int value, Entry pre, Entry next) { this.value = value; this.pre = pre; this.next = next; } public void addNext(Entry e) { e.next = next; e.pre = this; if (next != null) next.pre = e; next = e; } public void addPre(Entry e) { e.next = this; e.pre = pre; if (pre != null) pre.next = e; pre = e; } public Entry remove() { if (pre != null) pre.next = next; if (next != null) next.pre = pre; pre = null; Entry n = next; next = null; return n; } public void clear() { while (next != null) { next = next.remove(); } } public void swap(Entry e) { if (e == null) return; value = (e.value + value) - (e.value = value); } public String toString() { return String.valueOf(value); } } private static Entry bucketsA[] = new Entry[10]; private static Entry bucketsB[] = new Entry[10]; static { for (int i = 0; i < 10; i++) { bucketsA[i] = new Entry(0); bucketsB[i] = new Entry(0); } } public static void addToList(Entry head, Entry e, int t) { Entry p = head; while (p.next != null) { if ((p.next.value / t) % 10 > (e.value / t) % 10) { p.next.addPre(e); break; } p = p.next; } if (p.next == null && (p.value / t) % 10 <= (e.value / t) % 10) { p.addNext(e); } } public static int[] CollectResult(int a[]) { int index = 0; for (int j = 0; j < bucketsA.length; j++) { Entry p = bucketsA[j].next; while (p != null) { a[index++] = p.value; p = p.next; } } return a; } public void sort(int a[], int radix) { for (int j = 0; j < bucketsA.length; j++) { bucketsA[j].clear(); } for (int i = 0; i < a.length; i++) { addToList(bucketsA[a[i] % 10], new Entry(a[i]), 1); } int t = 10; for (int i = 1; i < radix; i++) { Entry[] bucketsC = bucketsA;// swap bucketsA = bucketsB; bucketsB = bucketsC; for (int j = 0; j < bucketsA.length; j++) { bucketsA[j].clear(); } for (int j = 0; j < bucketsB.length; j++) { while (bucketsB[j].next != null) { Entry e = bucketsB[j].next; bucketsB[j].next.remove(); addToList(bucketsA[(e.value / t) % 10], e, t); } } t *= 10; } CollectResult(a); SortUtils.print(a); } public void sort(int a[]){ sort(a, 3); } public static void main(String[] args) { new RadixSort().sort(new int[] { 329, 457, 657, 839, 436, 720, 355 }, 3); } }这里使用了两组桶,其效果可能会比正常的基数排序要差,但是基数的期望复杂度是O(n)。
总结
类别 |
排序方法 |
时间复杂度 |
空间复杂度 |
稳定性 |
||
平均 |
最好 |
最坏 |
||||
插入排序 |
直接插入 |
O(n2) |
O(n) |
O(n2) |
O(1) |
稳定 |
|
Shell排序 |
O(n1.3) |
O(n) |
O(n2) |
O(1) |
不稳定 |
选择排序 |
直接选择 |
O(n2) |
O(n2) |
O(n2) |
O(1) |
不稳定 |
|
堆排序 |
O(nlgn) |
O(nlgn) |
O(nlgn) |
O(1) |
不稳定 |
交换排序 |
冒泡排序 |
O(n2) |
O(n) |
O(n2) |
O(1) |
稳定 |
|
快速排序 |
O(nlgn) |
O(nlgn) |
O(n2) |
O(nlgn) |
不稳定 |
归并排序 |
|
O(nlgn) |
O(nlgn) |
O(nlgn) |
n |
稳定 |
基数排序 |
|
O(d(r+n)) |
O(d(n+rd)) |
O(d(r+n)) |
O(rd+n) |
稳定 |
r表示关键字的基数,d表示长度,n表示关键字个数。
稳定排序包括:直接插入、冒泡排序、归并排序、基数排序;基数排序依赖于稳定的排序方式。
附:
public interface Sort { public void sort(int a[]); }
public class SortUtils { public static void swap(int a[], int i, int j){ a[i] = (a[i] + a[j])-(a[j]=a[i]); } public static void print(int a[]){ System.out.println(Arrays.toString(a)); } public static Random static_rand = new Random(); public static Random rand = new Random(37); public static int[] generate(int seed, int len){ static_rand.setSeed(seed); int a[] = new int[len]; for(int i =0 ; i < len; i++){ a[i] = static_rand.nextInt(1000); } //System.out.print("Generated: "); print(a); return a; } public static int[] generate(int len){ int a[] = new int[len]; for(int i =0 ; i < len; i++){ a[i] = rand.nextInt(1000); } //System.out.print("Generated: "); print(a); return a; } }