1、选择排序
对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的例句只有一个时为止。每一轮结束后都有一个数放在了它最后应该在的位置。
public class SelectSort { public static void main(String[] args) { int a[] = {5,4,9,8,7,6,0,2,1,3}; selectSort(a); for(int i = 0; i < a.length; i ++) { System.out.print(a[i] + " "); } } private static void selectSort(int[] a) { int temp = 0; int flag = 0; for(int i = 0; i < a.length; i ++) { temp = a[i]; flag = i; for(int j = i + 1; j < a.length; j ++) { if(temp > a[j]) { temp = a[j]; flag = j; } } if(flag != i) { a[flag] = a[i]; a[i] = temp; } } } }
2、直接插入排序
对于给定的一组记录，初始时假设第一个记录自成一个有序序列，其余记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。
public class InsertSort { public static void main(String[] args) { int a[] = {5,2,4,6,7,1,8,3,9,0}; insertSort(a); for(int i = 0; i < a.length; i ++) { System.out.print(a[i] + " "); } } private static void insertSort(int[] a) { for(int i = 1; i < a.length; i ++) { int temp = a[i]; int j = i; if(a[j - 1] > temp) { while(j >= 1 && a[j - 1] > temp) { a[j] = a[j - 1]; j--; } } a[j] = temp; } } }
3、冒泡排序
由小到大为例，对于给定的n个记录，从第一个记录开始，依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换位置，进行一轮比较和换位后，n个记录中的最大记录将位于第n位；然后对前（n-1）个记录进行第二轮比较；重复该过程直到进行比较时记录只剩下一个为止。每一趟结束后都有一个数位于它最终应在的位置。
public class BubbleSort { public static void main(String[] args) { int a[] = {2,4,6,3,1,7,5,0,9,8}; bubbleSort(a); for(int i = 0; i < a.length; i ++) { System.out.print(a[i] + " "); } } private static void bubbleSort(int[] a) { int temp; for(int i = 0; i < a.length; i ++) { for(int j = a.length - 1; j > i; j --) { if(a[j] < a[j - 1]) { temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; } } } } }
4、归并排序
对于给定的一组记录（假设n个），首先将每两个相邻的长度为1的子序列进行归并，得到n/2（向上取整）个长度为2或1的有序子序列，再将其两两归并，反复执行此过程，直到得到一个有序序列。第一步：划分子表；第二步：合并半子表。
public class MergeSort { public static void main(String[] args) { int a[] = {5,3,8,4,9,2,1,0,7,6}; mergeSort(a, 0, a.length - 1); for(int i = 0; i < a.length; i ++) { System.out.print(a[i] + " "); } } private static void mergeSort(int[] a, int p, int r) { if(p < r) { int q = (p + r) / 2; mergeSort(a, p, q); mergeSort(a, q + 1, r); merge(a, p, q, r); } } private static void merge(int[] a, int p, int q, int r) { int i, j, k, n1, n2; n1 = q - p + 1; n2 = r - q; int[] L = new int[n1]; int[] R = new int[n2]; for(i = 0, k = p; i < n1; i ++, k ++) L[i] = a[k]; for(i = 0, k = q + 1; i < n2; i ++, k ++) R[i] = a[k]; for(k = p, i = 0, j = 0; i < n1 && j < n2; k ++) { if(L[i] > R[j]) { a[k] = L[i]; i ++; }else { a[k] = R[j]; j ++; } } if(i < n1) { for(j = i; j < n1; j ++, k ++) a[k] = L[j]; } if(j < n2) { for(i = j; i < n2; i ++, k ++) a[k] = R[i]; } } }
5、快速排序
对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。
①从右向左找第一个大于基准的数，交换位置
②从左向右找第一个小于基准的数，交换位置
每一趟排序之后必定能找到一个数，它的左面都比它小，它的右面都比它大。
public class QuickSort { public static void main(String[] args) { int a[] = {3,6,9,5,7,2,1,0,8,4}; quickSort(a); for(int i = 0; i < a.length; i ++) { System.out.print(a[i] + " "); } } private static void quickSort(int[] a) { sort(a, 0, a.length - 1); } private static void sort(int[] a, int low, int high) { if(low >= high) { return; } int i = low; int j = high; int index = a[i]; while(i < j) { while(i < j && a[j] >= index) j --; if(i < j) a[i ++] = a[j]; while(i < j && a[i] < index) i ++; if(i < j) a[j --] = a[i]; } a[i] = index; sort(a, low, i - 1); sort(a, i + 1, high); } }
6、希尔排序
先将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序后”，最后再对所有元素进行一次直接插入排序。
步骤：
①选择一个步长序列t1，t2，···，tk，满足ti > tj（i<j），tk=1。
②按步长序列个数k，对待排序序列进行k趟排序。
③每趟排序，根据对应的步长ti，将待排序列分割成ti个子序列，分别对各个子序列进行直接插入排序。
public class ShellSort { public static void main(String[] args) { int a[] = {3,6,9,5,7,2,1,0,8,4}; shellSort(a); for(int i = 0; i < a.length; i ++) { System.out.print(a[i] + " "); } } private static void shellSort(int[] a) { int len = a.length; int i, j, h, temp; for(h = len / 2; h > 0; h = h / 2) { for(i = h; i < len; i ++) { temp = a[i]; for(j = i - h; j >= 0; j -= h) { if(temp < a[j]) { a[j + h] = a[j]; }else break; } a[j + h] = temp; } } } }
7、堆排序
对于给定的n个记录，初始时把这些记录看作一颗顺序存储的二叉树，然后将其调整为一个大顶堆，然后将堆的最后一个元素与堆顶元素（即二叉树的根结点）进行交换后，堆的最后一个元素即为最大元素；接着将前（n-1）个元素（即不包括最大记录）重新调整为一个大顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次大的记录，重复该过程直到调整的堆中只剩一个元素时为止，该元素即为最小记录，此时可得到一个有序序列。
public class HeapSort { public static void main(String[] args) { int a[] = {3,6,9,5,7,2,1,0,8,4}; heapSort(a); for(int i = 0; i < a.length; i ++) { System.out.print(a[i] + " "); } } private static void heapSort(int[] a) { int i; int len = a.length; for(i = len / 2 - 1; i >= 0; i --) adjustHeap(a, i, len - 1); for(i = len - 1; i >= 0; i --) { int temp = a[0]; a[0] = a[i]; a[i] = temp; adjustHeap(a, 0, i - 1); } } private static void adjustHeap(int[] a, int pos, int len) { int temp; int child; for(temp = a[pos]; 2 * pos + 1 <= len; pos = child) { child = 2 * pos + 1; if(child < len && a[child] > a[child + 1]) child ++; if(a[child] < temp) a[pos] = a[child]; else break; } a[pos] = temp; } }
算法性能对比
虽然直接插入排序和冒泡排序的速度比较慢，但是当初始序列整体或局部有序时，这两种排序算法会有较高的效率。当初始序列整体有序或局部有序时，快速排序算法的效率会下降。当排序序列较小且不要求稳定性时，直接选择排序效率较好；要求稳定性时，冒泡排序效率较好。堆排序适合应用在找出很多记录中的n个最小值或最大值，如找出10000个记录中最小的10个。