待排序的元素需要实现 Java 的 Comparable 接口，该接口有 compareTo() 方法，可以用它来判断两个元素的大小关系。
研究排序算法的成本模型时，计算的是 比较和交换的次数。
使用辅助函数 less() 和 swap() 来进行比较和交换的操作，使得代码的可读性和可移植性更好。
public abstract class Sort<T extends Comparable<T>> { public abstract void sort(T[] nums); protected boolean less(T v, T w) { return v.compareTo(w) < 0; } protected void swap(T[] a, int i, int j) { T t = a[i]; a[i] = a[j]; a[j] = t; } }
1、选择排序(Select Sort)
常规的方法：
import java.util.Arrays; //选择排序:先定义一个记录最小元素的下标，然后循环一次后面的，找到最小的元素，最后将他放到前面排序好的序列。 public class SelectSort_02 { public static void main(String[] args) { int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}; for (int i = 0; i < a.length-1; i++) { int index=i;//标记第一个为待比较的数 for (int j = i+1; j < a.length; j++) { //然后从后面遍历与第一个数比较 if (a[j]<a[index]) { //如果小,就交换最小值 index=j;//保存最小元素的下标 } } //找到最小值后，将最小的值放到第一的位置，进行下一遍循环 int temp=a[index]; a[index]=a[i]; a[i]=temp; } System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] } }
使用辅助函数：
public class Selection<T extends Comparable<T>> extends Sort<T> { @Override public void sort(T[] nums) { int N = nums.length; for (int i = 0; i < N; i++) { int min = i; for (int j = i + 1; j < N; j++) if (less(nums[j], nums[min])) min = j; swap(nums, i, min); } } }
选择排序需要 ~N2/2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。
2、冒泡排序(Bubble Sort)
通过从左到右不断交换相邻逆序的相邻元素，在一轮的交换之后，可以让未排序的元素上浮到右侧。
在一轮循环中，如果没有发生交换，就说明数组已经是有序的，此时可以直接退出。
import java.util.Arrays; //冒泡排序 public class BubbleSort_01 { public static void main(String[] args) { int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}; //记录比较次数 int count=0; //i=0,第一轮比较 for (int i = 0; i < a.length-1; i++) { //第一轮，两两比较 for (int j = 0; j < a.length-1-i; j++) { if (a[j]>a[j+1]) { int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } count++; } } System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] System.out.println("一共比较了："+count+"次");//一共比较了：105次 } }
冒泡排序的优化：
import java.util.Arrays; public class BubbleSort1_01 { public static void main(String[] args) { int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}; int count=0; for (int i = 0; i < a.length-1; i++) { boolean flag=true; for (int j = 0; j < a.length-1-i; j++) { if (a[j]>a[j+1]) { int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; flag=false; } count++; } if (flag) { break; } } System.out.println(Arrays.toString(a));// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] System.out.println("一共比较了："+count+"次");//一共比较了：95次 } }
辅助函数方法：
public class Bubble<T extends Comparable<T>> extends Sort<T> { @Override public void sort(T[] nums) { int N = nums.length; boolean hasSorted = false; for (int i = 0; i < N && !hasSorted; i++) { hasSorted = true; for (int j = 0; j < N - i - 1; j++) { if (less(nums[j + 1], nums[j])) { hasSorted = false; swap(nums, j, j + 1); } } } } }
3、插入排序(Insert Sort)
插入排序从左到右进行，每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左部数组依然有序。
第 j 元素是通过不断向左比较并交换来实现插入过程：当第 j 元素小于第 j - 1 元素，就将它们的位置交换，然后令 j指针向左移动一个位置，不断进行以上操作。
import java.util.Arrays; //插入排序:定义一个待插入的数，再定义一个待插入数的前一个数的下标，然后拿待插入数与前面的数组一一比较，最后交换。 public class InsertSort_03 { public static void main(String[] args) { int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}; for (int i = 0; i < a.length; i++) { //长度不减1，是因为要留多一个位置方便插入数 //定义待插入的数 int insertValue=a[i]; //找到待插入数的前一个数的下标 int insertIndex=i-1; while (insertIndex>=0 && insertValue <a[insertIndex]) {//拿a[i]与a[i-1]的前面数组比较 a[insertIndex+1]=a[insertIndex]; insertIndex--; } a[insertIndex+1]=insertValue; } System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] } }
辅助函数方法：
public class Insertion<T extends Comparable<T>> extends Sort<T> { @Override public void sort(T[] nums) { int N = nums.length; for (int i = 1; i < N; i++) for (int j = i; j > 0 && less(nums[j], nums[j - 1]); j--) swap(nums, j, j - 1); } }
对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相
邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。
插入排序的复杂度取决于数组的初始顺序，如果数组已经部分有序了，逆序较少，那么插入排序会很快。
平均情况下插入排序需要 ~N2/4 比较以及 ~N2/4 次交换；
最坏的情况下需要 ~N2/2 比较以及 ~N2/2次交换，最坏的情况是数组是倒序的；
最好的情况下需要 N-1 次比较和 0 次交换，最好的情况就是数组已经有序了。
4、希尔排序(Shell Sort)
对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。
希尔排序的出现就是为了改进插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于1。
希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。
public class Shell<T extends Comparable<T>> extends Sort<T> { @Override public void sort(T[] nums) { int N = nums.length; int h = 1; while (h < N / 3) h = 3 * h + 1; // 1, 4, 13, 40, ... while (h >= 1) { for (int i = h; i < N; i++) for (int j = i; j >= h && less(nums[j], nums[j - h]); j -= h) swap(nums, j, j - h); h = h / 3; } } }
希尔排序的运行时间达不到平方级别，使用递增序列 1, 4, 13, 40, … 的希尔排序所需要的比较次数不会超过 N 的若干倍乘于递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。
常规代码：
import java.util.Arrays; //希尔排序：插入排序的升级 public class ShellSort_04 { public static void main(String[] args) { int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}; int count=0;//比较次数 for (int gap=a.length / 2; gap > 0; gap = gap / 2) { //将整个数组分为若干个子数组 for (int i = gap; i < a.length; i++) { //遍历各组的元素 for (int j = i - gap; j>=0; j=j-gap) { //交换元素 if (a[j]>a[j+gap]) { int temp=a[j]; a[j]=a[j+gap]; a[j+gap]=temp; count++; } } } } System.out.println(count);//16 System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] } }
5、归并排序(Merge Sort）
归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。
常规代码：
import java.util.Arrays; //归并排序 public class MergeSort_06 { public static void main(String[] args) { int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}; //int a[]={5,2,4,7,1,3,2,2}; int temp[]=new int[a.length]; mergesort(a,0,a.length-1,temp); System.out.println(Arrays.toString(a)); } private static void mergesort(int[] a, int left, int right, int[] temp) { //分解 if (left<right) { int mid=(left+right)/2; //向左递归进行分解 mergesort(a, left, mid, temp); //向右递归进行分解 mergesort(a, mid+1, right, temp); //每分解一次便合并一次 merge(a,left,right,mid,temp); } } /** * * @param a 待排序的数组 * @param left 左边有序序列的初始索引 * @param right 右边有序序列的初始索引 * @param mid 中间索引 * @param temp 做中转的数组 */ private static void merge(int[] a, int left, int right, int mid, int[] temp) { int i=left; //初始i，左边有序序列的初始索引 int j=mid+1;//初始化j，右边有序序列的初始索引（右边有序序列的初始位置即中间位置的后一位置） int t=0;//指向temp数组的当前索引，初始为0 //先把左右两边的数据（已经有序）按规则填充到temp数组 //直到左右两边的有序序列，有一边处理完成为止 while (i<=mid && j<=right) { //如果左边有序序列的当前元素小于或等于右边的有序序列的当前元素，就将左边的元素填充到temp数组中 if (a[i]<=a[j]) { temp[t]=a[i]; t++;//索引向后移 i++;//i后移 }else { //反之，将右边有序序列的当前元素填充到temp数组中 temp[t]=a[j]; t++;//索引向后移 j++;//j后移 } } //把剩余数据的一边的元素填充到temp中 while (i<=mid) { //此时说明左边序列还有剩余元素 //全部填充到temp数组 temp[t]=a[i]; t++; i++; } while (j<=right) { //此时说明左边序列还有剩余元素 //全部填充到temp数组 temp[t]=a[j]; t++; j++; } //将temp数组的元素复制到原数组 t=0; int tempLeft=left; while (tempLeft<=right) { a[tempLeft]=temp[t]; t++; tempLeft++; } } }
1. 归并方法
归并方法将数组中两个已经排序的部分归并成一个。
public abstract class MergeSort<T extends Comparable<T>> extends Sort<T> { protected T[] aux; protected void merge(T[] nums, int l, int m, int h) { int i = l, j = m + 1; for (int k = l; k <= h; k++) aux[k] = nums[k]; // 将数据复制到辅助数组 for (int k = l; k <= h; k++) { if (i > m) nums[k] = aux[j++]; else if (j > h) nums[k] = aux[i++]; else if (aux[i].compareTo(nums[j]) <= 0) nums[k] = aux[i++]; // 先进行这一步，保证稳定性 else nums[k] = aux[j++]; } } }
2. 自顶向下归并排序
public class Up2DownMergeSort<T extends Comparable<T>> extends MergeSort<T> { @Override public void sort(T[] nums) { aux = (T[]) new Comparable[nums.length]; sort(nums, 0, nums.length - 1); } p rivate void sort(T[] nums, int l, int h) { if (h <= l) return; int mid = l + (h - l) / 2; sort(nums, l, mid); sort(nums, mid + 1, h); merge(nums, l, mid, h); } }
因为每次都将问题对半分成两个子问题，而这种对半分的算法复杂度一般为 O(NlogN)，因此该归并排序方法的时间复杂度也为 O(NlogN)。
3. 自底向上归并排序
先归并那些微型数组，然后成对归并得到的微型数组。
public class Down2UpMergeSort<T extends Comparable<T>> extends MergeSort<T> { @Override public void sort(T[] nums) { int N = nums.length; aux = (T[]) new Comparable[N]; for (int sz = 1; sz < N; sz += sz) for (int lo = 0; lo < N - sz; lo += sz + sz) merge(nums, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1)); } }
