插入排序
1、原理：在有序数组中从后向前扫描找到要插入元素的位置，将元素插入进去。
2、步骤：插入元素和依次和前一个元素进行比较，若比前一个元素小就交换位置，否则结束循环。
3、代码：
package ecut.sort; import java.util.ArrayList; import java.util.List; import java.util.Scanner; import edu.princeton.cs.algs4.StdOut; /** * * 插入排序是将数组中无序数中依次和有序数进行比较，直到插入到正确的位置。 * 需要n-1趟完成排序，比较次数最坏是1+2.....+(n-1)即n(n-1)/2 ~ n^2/2次,最好是n-1次比较。 * 交换次数最坏是1+2.....+(n-1)即n(n-1)/2 ~ n^2/2次,最好是0次交换。时间复杂度是O(n^2)。 */ public class InsertionSort { private static Scanner sc;
@SuppressWarnings("rawtypes") public static void sort(Comparable[] a) { int N = a.length; for (int i = 1; i < N; i++) { for (int j = i - 1; j >= 0 && less(a[j + 1], a[j]); j--) { exch(a, j + 1, j); } } } @SuppressWarnings({ "rawtypes", "unchecked" }) public static boolean less(Comparable v, Comparable w) { // v.compareTo(w):v<w 返回负整数 v=w 返回0 v>w 返回正整数 return v.compareTo(w) < 0; } @SuppressWarnings("rawtypes") public static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } @SuppressWarnings("rawtypes") public static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.print(a[i] + " "); } StdOut.println(); } @SuppressWarnings("rawtypes") public static boolean isSorted(Comparable[] a) { for (int i = 1; i < a.length; i++) { if (less(a[i], a[i - 1])) { return false; } } return true; } public static void main(String[] args) { sc = new Scanner(System.in); String[] a = null; List<String> list = new ArrayList<String>(); while(sc.hasNextLine()){ list.add(sc.nextLine()); } a=list.toArray(new String[0]); sort(a); assert isSorted(a); show(a); } }
排序方法等价于：
@SuppressWarnings("rawtypes")
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 1; i < N; i++) {
//用k记录当前的位置
int k = i;
for (int j = i - 1; j >= 0; j--) {
if (less(a[k], a[j])) {
exch(a, k, j);//k=i,j=i-1 ===> k=j+1
//交换后要让k重新指向插入元素的位置
k--;
}else{
break;
}
}
}
}
插入排序是将数组中无序数中依次和有序数进行比较，直到插入到正确的位置。需要n-1趟完成排序，比较次数最坏是1+2.....+(n-1)即n(n-1)/2 ~ n^2/2次，最好是n-1次比较。交换次数最坏是1+2.....+(n-1)即n(n-1)/2 ~ n^2/2次，最好是0次交换。时间复杂度是O(n^2)。
选择排序
1、原理：依次从数组中选出最小的放入到对应位置。
2、步骤：找出数组中的最小值，和对应位置的元素进行交换，最小的和a[0]交换，其次小的和a[1]交换，以此类推。
3、代码：
package ecut.sort; import java.util.ArrayList; import java.util.List; import java.util.Scanner; import edu.princeton.cs.algs4.StdOut; /** * * 选择排序是依次选择数组中无序数中最小的和对应的数交换位置，最小的数和a[0]交换，第二小的和a[1]交换，以此类推。 * 需要n-1趟完成排序，比较次数是1+2.....+(n-1)即n(n-1)/2 ~ n^2/2次，n-1次交换，时间复杂度是O(n^2) * */ public class SelectionSort { private static Scanner sc; @SuppressWarnings("rawtypes") public static void sort(Comparable[] a) { int N = a.length; for (int i = 0; i < N - 1; i++) { int min = i; for (int j = i + 1; j < N; j++) { if (less(a[j], a[min])) { min = j; } } exch(a, i, min); } } @SuppressWarnings({ "rawtypes", "unchecked" }) public static boolean less(Comparable v, Comparable w) { // v.compareTo(w):v<w 返回负整数 v=w 返回0 v>w 返回正整数 return v.compareTo(w) < 0; } @SuppressWarnings("rawtypes") public static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } @SuppressWarnings("rawtypes") public static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.print(a[i] + " "); } StdOut.println(); } @SuppressWarnings("rawtypes") public static boolean isSorted(Comparable[] a) { for (int i = 1; i < a.length; i++) { if (less(a[i], a[i - 1])) { return false; } } return true; } public static void main(String[] args) { sc = new Scanner(System.in); String[] a = null; List<String> list = new ArrayList<String>(); while(sc.hasNextLine()){ list.add(sc.nextLine()); } a=list.toArray(new String[0]); sort(a); assert isSorted(a); show(a); } }
需要n-1趟完成排序，比较次数是1+2.....+(n-1)即n(n-1)/2 ~ n^2/2次，n-1次交换，时间复杂度是O(n^2)
归并排序
1、原理：将两个有序数组合并成一个新的有序数组。
2、步骤：对数组进行折半，分别对两边数组进行归并排序，先讲需要排序的数组拷贝到一个新数组中，然后比较mid+1和low所对应的值，将较小的数放入到拷贝数组中，以此类推。
3、代码：
package ecut.sort; import java.util.ArrayList; import java.util.List; import java.util.Scanner; import edu.princeton.cs.algs4.StdOut; /** * * 归并排序是将两个有序的数组合并到一个数组中。 * 数组长度为n的数组，比较次数所形成的二叉树有n层，总节点数是N=2^n-1，n=lgN+1 ~ lgN,比较次数最坏是n*2^n次即NlgN,最好是1/2 NlgN次比较。 * 时间复杂度是O(n log n) */ public class MergeSort { private static Scanner sc; @SuppressWarnings("rawtypes") private static Comparable[] aux; @SuppressWarnings("rawtypes") public static void sort(Comparable[] a) { aux = new Comparable[a.length]; sort(a,0,a.length-1); } @SuppressWarnings("rawtypes") public static void sort(Comparable[] a,int lo,int hi){ if(hi<=lo) return; int mid =lo+ (hi-lo)/2; sort(a,lo,mid); sort(a,mid+1,hi); merge(a,lo,mid,hi); } @SuppressWarnings("rawtypes") public static void merge(Comparable[] a,int lo, int mid,int hi){ int i=lo; int j=mid+1; for(int k=lo;k<=hi;k++){ aux[k]=a[k]; } 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++]; } } @SuppressWarnings({ "rawtypes", "unchecked" }) public static boolean less(Comparable v, Comparable w) { // v.compareTo(w):v<w 返回负整数 v=w 返回0 v>w 返回正整数 return v.compareTo(w) < 0; } @SuppressWarnings("rawtypes") public static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.print(a[i] + " "); } StdOut.println(); } @SuppressWarnings("rawtypes") public static boolean isSorted(Comparable[] a) { for (int i = 1; i < a.length; i++) { if (less(a[i], a[i - 1])) { return false; } } return true; } public static void main(String[] args) { sc = new Scanner(System.in); String[] a = null; List<String> list = new ArrayList<String>(); while(sc.hasNextLine()){ list.add(sc.nextLine()); } a=list.toArray(new String[0]); sort(a); assert isSorted(a); show(a); } }
归并排序是将两个有序的数组合并到一个数组中。数组长度为n的数组，比较次数所形成的二叉树有n层，总节点数是N=2^n-1，n=lgN+1 ~ lgN,比较次数最坏是n*2^n次即NlgN,最好是1/2 NlgN次比较。 时间复杂度是O(n log n)。
冒泡排序
1、原理：依次比较相邻两个数的大小，最大的i数沉到zu
2、步骤：每趟排序中依次比较相邻两个数的大小，a[0]和a[1]比较，a[1]和a[2]比较，以此类推，直至结束，然后重复执行，直到所有的书有序。
3、代码：
package ecut.sort; import java.util.ArrayList; import java.util.List; import java.util.Scanner; import edu.princeton.cs.algs4.StdOut; /** * * 冒泡排序是将数组依次比较相邻的两个数，将小数放在前面，大数放在后面。 * 需要n-1趟完成排序，比较次数最坏是1+2.....+(n-1)即n(n-1)/2 ~ n^2/2次,时间复杂度是O(n^2)。 */ public class BubbleSort { private static Scanner sc; @SuppressWarnings("rawtypes") public static void sort(Comparable[] a) { for(int i=0; i<a.length-1;i++){ for(int j=0; j<a.length-i-1;j++){ if(less(a[j+1],a[j])){ exch(a,j+1,j); } } } } @SuppressWarnings({ "rawtypes", "unchecked" }) public static boolean less(Comparable v, Comparable w) { // v.compareTo(w):v<w 返回负整数 v=w 返回0 v>w 返回正整数 return v.compareTo(w) < 0; } @SuppressWarnings("rawtypes") public static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } @SuppressWarnings("rawtypes") public static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.print(a[i] + " "); } StdOut.println(); } @SuppressWarnings("rawtypes") public static boolean isSorted(Comparable[] a) { for (int i = 1; i < a.length; i++) { if (less(a[i], a[i - 1])) { return false; } } return true; } public static void main(String[] args) { sc = new Scanner(System.in); String[] a = null; List<String> list = new ArrayList<String>(); while(sc.hasNextLine()){ list.add(sc.nextLine()); } a=list.toArray(new String[0]); sort(a); assert isSorted(a); show(a); } }
冒泡排序是将数组依次比较相邻的两个数，将小数放在前面，大数放在后面。需要n-1趟完成排序，比较次数最坏是1+2.....+(n-1)即n(n-1)/2 ~ n^2/2次，时间复杂度是O(n^2)。
快速排序
1、原理：找到一个目标元素，把比目标元素小的数放在目标元素的左侧，比目标元素大的数放在目标元素的右侧。
2、步骤：将 i 赋值为需要排序元素的初始位置，将 j 指向数组的末尾位置+1，然后让 i 依次后移，j 依次前移，若 j 所指向位置的元素比目标元素小就退出while循环，若 i 所指向位置的元素比目标元素大就退出while循环，然后交换两个元素。分别对数组的左半边和右半边都进行排序。
3、代码：
package ecut.sort; import java.util.ArrayList; import java.util.List; import java.util.Scanner; import edu.princeton.cs.algs4.StdOut; import edu.princeton.cs.algs4.StdRandom; /** * * 快速排序是将数组切分使左侧小于a[j],右侧大于a[j]。 * 时间复杂度是O(n log n) * */ public class QuickSort { private static Scanner sc; @SuppressWarnings("rawtypes") public static void sort(Comparable[] a) { StdRandom.shuffle(a);//清楚对输入的依赖 sort(a,0,a.length-1); } @SuppressWarnings("rawtypes") public 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); } @SuppressWarnings("rawtypes") public static int partition(Comparable[] a,int lo,int hi){ Comparable v = a[0]; int i = lo; int j = hi+1; while(true){ while(less(a[++i],v)){ if(i==hi){ break; } } while(less(v,a[--j])){ if(j==lo){ break; } } if(i>=j){ break; } exch(a,i,j); } exch(a,lo,j); return j; } @SuppressWarnings("rawtypes") public static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } @SuppressWarnings({ "rawtypes", "unchecked" }) public static boolean less(Comparable v, Comparable w) { // v.compareTo(w):v<w 返回负整数 v=w 返回0 v>w 返回正整数 return v.compareTo(w) < 0; } @SuppressWarnings("rawtypes") public static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.print(a[i] + " "); } StdOut.println(); } @SuppressWarnings("rawtypes") public static boolean isSorted(Comparable[] a) { for (int i = 1; i < a.length; i++) { if (less(a[i], a[i - 1])) { return false; } } return true; } public static void main(String[] args) { sc = new Scanner(System.in); String[] a = null; List<String> list = new ArrayList<String>(); while(sc.hasNextLine()){ list.add(sc.nextLine()); } a=list.toArray(new String[0]); sort(a); assert isSorted(a); show(a); } }
快速排序的时间复杂度是O(n log n)。
转载请于明显处标明出处
https://www.cnblogs.com/AmyZheng/p/9502759.html
推荐博客链接
https://www.cnblogs.com/onepixel/articles/7674659.html
原文：https://www.cnblogs.com/AmyZheng/p/9502759.html