赞
踩
什么是算法
解决问题的方法
五大特性
有限性
确定性
可行性
输入
输出
什么是数据结构
研究的是数据如何在计算机中进行组织和存储,使得我们可以高效的获取数据获取修改数据
选择排序
public class Sort { public static void mySort(int[] arr) { for (int i = 0; i < arr.length; i++) { int temp = arr[i]; int index = 0; for (int j = i + 1; j < arr.length; j++) { if (arr[i] > arr[j]) { arr[i] = arr[j]; index = j; } } if (index != 0) { arr[index] = temp; } } for (int i : arr) { System.out.println(i); } } public static void sort(int[] arr) { // arr[0...i) 是有序的;arr[i...n) 是无序的 for (int i = 0; i < arr.length; i++) { // 选择 arr[i...n) 中的最小值的索引 int minIndex = i; for (int j = i; j < arr.length; j++) { if (arr[j] < arr[minIndex]) minIndex = j; } swap(arr, i, minIndex); } for (int i : arr) { System.out.println(i); } } private static void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static void main(String[] args) { int[] a = { 6, 4, 2, 3, 1, 5 }; // mySort(a); sort(a); } }
使用泛型
public class SelectionSort { private SelectionSort() { } public static <E extends Comparable<E>> void sort(E[] arr) { // arr[0...i) 是有序的;arr[i...n) 是无序的 for (int i = 0; i < arr.length; i++) { // 选择 arr[i...n) 中的最小值 int minIndex = i; for (int j = i; j < arr.length; j++) { if (arr[j].compareTo(arr[minIndex]) < 0) minIndex = j; } swap(arr, i, minIndex); } } private static <E> void swap(E[] arr, int i, int j) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static void main(String[] args) { Integer[] arr = { 1, 4, 2, 3, 6, 5 }; SelectionSort.sort(arr); for (int e : arr) System.out.print(e + " "); System.out.println(); } }
对象实现 comparable 接口,使得类对象可以使用选择排序算法
public class SelectionSort { private SelectionSort() { } public static <E extends Comparable<E>> void sort(E[] arr) { // arr[0...i) 是有序的;arr[i...n) 是无序的 for (int i = 0; i < arr.length; i++) { // 选择 arr[i...n) 中的最小值 int minIndex = i; for (int j = i; j < arr.length; j++) { if (arr[j].compareTo(arr[minIndex]) < 0) minIndex = j; } swap(arr, i, minIndex); } } private static <E> void swap(E[] arr, int i, int j) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static void main(String[] args) { Integer[] arr = { 1, 4, 2, 3, 6, 5 }; SelectionSort.sort(arr); for (int e : arr) System.out.print(e + " "); System.out.println(); Student[] students = { new Student("Alice", 98), new Student("Bobo", 100), new Student("Charles", 66), }; SelectionSort.sort(students); for (Student student : students) System.out.print(student + " "); System.out.println(); } } public class Student implements Comparable<Student> { private String name; private int score; public Student(String name, int score) { this.name = name; this.score = score; } @Override public int compareTo(Student another) { // if(this.score < another.score) // return -1; // else if(this.score == another.score) // return 0; // return 1; // return this.score - another.score; return another.score - this.score; } @Override public boolean equals(Object student) { if (this == student) return true; if (student == null) return false; if (this.getClass() != student.getClass()) return false; Student another = (Student) student; return this.score == another.score; } @Override public String toString() { return String.format("Student(name: %s, score: %d)", name, score); } }
编写验证排序算法
public class SortingHelper { private SortingHelper() { } public static <E extends Comparable<E>> boolean isSorted(E[] arr) { for (int i = 1; i < arr.length; i++) if ( arr[i - 1].compareTo(arr[i]) > 0 ) return false; return true; } public static <E extends Comparable<E>> void sortTest( String sortname, E[] arr ) { long startTime = System.nanoTime(); if (sortname.equals("SelectionSort")) SelectionSort.sort(arr); long endTime = System.nanoTime(); double time = (endTime - startTime) / 1000000000.0; if (!SortingHelper.isSorted(arr)) throw new RuntimeException( sortname + " failed" ); System.out.println( String.format("%s , n = %d : %f s", sortname, arr.length, time) ); } } public class SelectionSort { private SelectionSort(){ } public static <E extends Comparable> void sort(E[] arr){ for(int i = 0; i < arr.length; i ++){ // 选择 arr[i...n) 中的最小值 int minIndex = i; for(int j = i; j < arr.length; j ++){ if(arr[j].compareTo(arr[minIndex]) < 0) minIndex = j; } swap(arr, i, minIndex); } } private static <E> void swap(E[] arr, int i, int j){ E t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static void main(String[] args){ int[] dataSize = { 10000, 100000}; for(int n: dataSize){ Integer[] arr = ArrayGenerator.generateRandomArray(n, n); SortingHelper.sortTest("SelectionSort", arr); } } } import java.util.Random; public class ArrayGenerator { private ArrayGenerator(){ } public static Integer[] generateOrderedArray(int n){ Integer[] arr = new Integer[n]; for(int i = 0; i < n; i ++) arr[i] = i; return arr; } // 生成一个长度为 n 的随机数组,每个数字的范围是 [0, bound) public static Integer[] generateRandomArray(int n, int bound){ Integer[] arr = new Integer[n]; Random rnd = new Random(); for(int i = 0; i < n; i ++) arr[i] = rnd.nextInt(bound); return arr; } }
选择排序算法的时间复杂度恒为 O(n^2)
插入
public class InsertionSort { private InsertionSort() { } public static <E extends Comparable<E>> void sort(E[] arr) { for (int i = 0; i < arr.length; i++) { // 将 arr[i] 插入到合适的位置 // for(int j = i; j - 1 >= 0; j --){ // if(arr[j].compareTo(arr[j - 1]) < 0) // swap(arr, j - 1, j); // else break; // } for (int j = i; j - 1 >= 0 && arr[j].compareTo(arr[j - 1]) < 0; j--) swap( arr, j - 1, j ); } } private static <E> void swap(E[] arr, int i, int j) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; } private static <E extends Comparable<E>> boolean isSorted(E[] arr) { for (int i = 1; i < arr.length; i++) if ( arr[i - 1].compareTo(arr[i]) > 0 ) return false; return true; } public static void main(String[] args) { int[] dataSize = { 10000, 100000 }; for (int n : dataSize) { Integer[] arr = ArrayGenerator.generateRandomArray(n, n); SortingHelper.sortTest("InsertionSort", arr); } } } 优化后 public static <E extends Comparable<E>> void sort2(E[] arr){ for(int i = 0; i < arr.length; i ++){ // 将 arr[i] 插入到合适的位置 E t = arr[i]; int j; for(j = i; j - 1 >= 0 && t.compareTo(arr[j - 1]) < 0; j --){ arr[j] = arr[j - 1]; } arr[j] = t; } }
对于已排序的数据,插入排序算法时间复杂度退化为 O(n)
冒泡
public class BubbleSort { private BubbleSort() { } public static <E extends Comparable<E>> void sort(E[] data) { for (int i = 0; i + 1 < data.length; i++) { // arr[n - i, n) 已排好序 // 通过冒泡在 arr[n - i - 1] 位置放上合适的元素 for (int j = 0; j + 1 <= data.length - i - 1; j++) if ( data[j].compareTo(data[j + 1]) > 0 ) swap(data, j, j + 1); } } private static <E> void swap(E[] arr, int i, int j) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static void main(String[] args) { int n = 100000; Integer[] arr = ArrayGenerator.generateRandomArray(n, n); SortingHelper.sortTest("BubbleSort", arr); } }
如果数组已经是顺序的,加入判断进行跳出
public static <E extends Comparable<E>> void sort2(E[] data){ for(int i = 0; i + 1 < data.length; i ++){ // arr[n - i, n) 已排好序 // 通过冒泡在 arr[n - i - 1] 位置放上合适的元素 boolean isSwapped = false; for(int j = 0; j < data.length - i - 1; j ++) if(data[j].compareTo(data[j + 1]) > 0){ swap(data, j, j + 1); isSwapped = true; } if(!isSwapped) break; } }
继续优化,第一轮排序后最后一个交换的位置后面已经排序好
public static <E extends Comparable<E>> void sort3(E[] data){ for(int i = 0; i + 1 < data.length; ){ // arr[n - i, n) 已排好序 // 通过冒泡在 arr[n - i - 1] 位置放上合适的元素 int lastSwappedIndex = 0; for(int j = 0; j < data.length - i - 1; j ++) if(data[j].compareTo(data[j + 1]) > 0){ swap(data, j, j + 1); lastSwappedIndex = j + 1; } i = data.length - lastSwappedIndex; } }
希尔排序
import java.util.Arrays; public class ShellSort { private ShellSort() { } public static <E extends Comparable<E>> void sort(E[] data) { int h = data.length / 2; while (h >= 1) { for (int start = 0; start < h; start++) { // 对 data[start, start + h, start + 2h, start + 3h ...], 进行插入排序 for (int i = start + h; i < data.length; i += h) { E t = data[i]; int j; for ( j = i; j - h >= 0 && t.compareTo(data[j - h]) < 0; j -= h ) data[j] = data[j - h]; data[j] = t; } } h /= 2; } } }
优化成两层循环
import java.util.Arrays; public class ShellSort { private ShellSort() { } public static <E extends Comparable<E>> void sort(E[] data) { int h = data.length / 2; while (h >= 1) { for (int i = h; i < data.length; i++) { E t = data[i]; int j; for ( j = i; j - h >= 0 && t.compareTo(data[j - h]) < 0; j -= h ) data[j] = data[j - h]; data[j] = t; } h /= 2; } } public static void main(String[] args) { int n = 1000000; Integer[] arr = ArrayGenerator.generateRandomArray(n, n); Integer[] arr2 = Arrays.copyOf(arr, arr.length); SortingHelper.sortTest("ShellSort", arr); SortingHelper.sortTest("MergeSort", arr2); } }
快速排序
import java.util.Arrays; import java.util.Random; public class QuickSort { private QuickSort() { } public static <E extends Comparable<E>> void sort(E[] arr) { sort(arr, 0, arr.length - 1); } private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) { if (l >= r) return; int p = partition(arr, l, r); sort(arr, l, p - 1); sort(arr, p + 1, r); } private static <E extends Comparable<E>> int partition( E[] arr, int l, int r ) { // 生成 [l, r] 之间的随机索引 int p = l + (new Random()).nextInt(r - l + 1); swap(arr, l, p); // arr[l+1...j] < v ; arr[j+1...i] >= v int j = l; for (int i = l + 1; i <= r; i++) if (arr[i].compareTo(arr[l]) < 0) { j++; swap(arr, i, j); } swap(arr, l, j); return j; } // 在 sort2 中,我们只创建一个 Random 类的对象 public static <E extends Comparable<E>> void sort2(E[] arr) { Random rnd = new Random(); sort2(arr, 0, arr.length - 1, rnd); } private static <E extends Comparable<E>> void sort2( E[] arr, int l, int r, Random rnd ) { if (l >= r) return; int p = partition2(arr, l, r, rnd); sort2(arr, l, p - 1, rnd); sort2(arr, p + 1, r, rnd); } private static <E extends Comparable<E>> int partition2( E[] arr, int l, int r, Random rnd ) { // 生成 [l, r] 之间的随机索引 int p = l + rnd.nextInt(r - l + 1); swap(arr, l, p); // arr[l+1...j] < v ; arr[j+1...i] >= v int j = l; for (int i = l + 1; i <= r; i++) if (arr[i].compareTo(arr[l]) < 0) { j++; swap(arr, i, j); } swap(arr, l, j); return j; } private static <E> void swap(E[] arr, int i, int j) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static void main(String[] args) { int n = 1000000; Integer[] arr = ArrayGenerator.generateRandomArray(n, n); Integer[] arr2 = Arrays.copyOf(arr, arr.length); Integer[] arr3 = Arrays.copyOf(arr, arr.length); SortingHelper.sortTest("MergeSort", arr); SortingHelper.sortTest("QuickSort", arr2); SortingHelper.sortTest("QuickSort2", arr3); } }
双路快速排序算法
import java.util.Arrays; import java.util.Random; public class QuickSort { private QuickSort() { } public static <E extends Comparable<E>> void sort(E[] arr) { Random rnd = new Random(); sort(arr, 0, arr.length - 1, rnd); } private static <E extends Comparable<E>> void sort( E[] arr, int l, int r, Random rnd ) { if (l >= r) return; int p = partition(arr, l, r, rnd); sort(arr, l, p - 1, rnd); sort(arr, p + 1, r, rnd); } private static <E extends Comparable<E>> int partition( E[] arr, int l, int r, Random rnd ) { // 生成 [l, r] 之间的随机索引 int p = l + rnd.nextInt(r - l + 1); swap(arr, l, p); // arr[l+1...j] < v ; arr[j+1...i] >= v int j = l; for (int i = l + 1; i <= r; i++) if (arr[i].compareTo(arr[l]) < 0) { j++; swap(arr, i, j); } swap(arr, l, j); return j; } public static <E extends Comparable<E>> void sort2ways(E[] arr) { Random rnd = new Random(); sort2ways(arr, 0, arr.length - 1, rnd); } private static <E extends Comparable<E>> void sort2ways( E[] arr, int l, int r, Random rnd ) { if (l >= r) return; int p = partition2ways(arr, l, r, rnd); sort2ways(arr, l, p - 1, rnd); sort2ways(arr, p + 1, r, rnd); } private static <E extends Comparable<E>> int partition2ways( E[] arr, int l, int r, Random rnd ) { // 生成 [l, r] 之间的随机索引 int p = l + rnd.nextInt(r - l + 1); swap(arr, l, p); // arr[l+1...i-1] <= v; arr[j+1...r] >= v int i = l + 1, j = r; while (true) { while (i <= j && arr[i].compareTo(arr[l]) < 0) i++; while (j >= i && arr[j].compareTo(arr[l]) > 0) j--; if (i >= j) break; swap(arr, i, j); i++; j--; } swap(arr, l, j); return j; } private static <E> void swap(E[] arr, int i, int j) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static void main(String[] args) { int n = 100000; Integer[] arr = ArrayGenerator.generateRandomArray(n, n); Integer[] arr2 = Arrays.copyOf(arr, arr.length); System.out.println("Random Array"); SortingHelper.sortTest("QuickSort", arr); SortingHelper.sortTest("QuickSort2Ways", arr2); System.out.println(); arr = ArrayGenerator.generateOrderedArray(n); arr2 = Arrays.copyOf(arr, arr.length); System.out.println("Ordered Array"); SortingHelper.sortTest("QuickSort", arr); SortingHelper.sortTest("QuickSort2Ways", arr2); System.out.println(); arr = ArrayGenerator.generateRandomArray(n, 1); arr2 = Arrays.copyOf(arr, arr.length); System.out.println("Same Value Array"); SortingHelper.sortTest("QuickSort", arr); SortingHelper.sortTest("QuickSort2Ways", arr2); System.out.println(); } }
三路快速排序算法
import java.util.Arrays; import java.util.Random; public class QuickSort { private QuickSort() { } public static <E extends Comparable<E>> void sort(E[] arr) { Random rnd = new Random(); sort(arr, 0, arr.length - 1, rnd); } private static <E extends Comparable<E>> void sort( E[] arr, int l, int r, Random rnd ) { if (l >= r) return; int p = partition(arr, l, r, rnd); sort(arr, l, p - 1, rnd); sort(arr, p + 1, r, rnd); } private static <E extends Comparable<E>> int partition( E[] arr, int l, int r, Random rnd ) { // 生成 [l, r] 之间的随机索引 int p = l + rnd.nextInt(r - l + 1); swap(arr, l, p); // arr[l+1...j] < v ; arr[j+1...i] >= v int j = l; for (int i = l + 1; i <= r; i++) if (arr[i].compareTo(arr[l]) < 0) { j++; swap(arr, i, j); } swap(arr, l, j); return j; } public static <E extends Comparable<E>> void sort2ways(E[] arr) { Random rnd = new Random(); sort2ways(arr, 0, arr.length - 1, rnd); } private static <E extends Comparable<E>> void sort2ways( E[] arr, int l, int r, Random rnd ) { if (l >= r) return; int p = partition2ways(arr, l, r, rnd); sort2ways(arr, l, p - 1, rnd); sort2ways(arr, p + 1, r, rnd); } private static <E extends Comparable<E>> int partition2ways( E[] arr, int l, int r, Random rnd ) { // 生成 [l, r] 之间的随机索引 int p = l + rnd.nextInt(r - l + 1); swap(arr, l, p); // arr[l+1...i-1] <= v; arr[j+1...r] >= v int i = l + 1, j = r; while (true) { while (i <= j && arr[i].compareTo(arr[l]) < 0) i++; while (j >= i && arr[j].compareTo(arr[l]) > 0) j--; if (i >= j) break; swap(arr, i, j); i++; j--; } swap(arr, l, j); return j; } public static <E extends Comparable<E>> void sort3ways(E[] arr) { Random rnd = new Random(); sort3ways(arr, 0, arr.length - 1, rnd); } private static <E extends Comparable<E>> void sort3ways( E[] arr, int l, int r, Random rnd ) { if (l >= r) return; /** 三路快速排序的 partition 过程 **/ // 生成 [l, r] 之间的随机索引 int p = l + rnd.nextInt(r - l + 1); swap(arr, l, p); // arr[l + 1, lt] < v, arr[lt + 1, i - 1] == v, arr[gt, r] > v int lt = l, i = l + 1, gt = r + 1; while (i < gt) { if (arr[i].compareTo(arr[l]) < 0) { lt++; swap(arr, i, lt); i++; } else if (arr[i].compareTo(arr[l]) > 0) { gt--; swap(arr, i, gt); } else { // arr[i] == v i++; } } swap(arr, l, lt); /** 三路快速排序的 partition 过程结束 **/ // 递归调用 sort3ways(arr, l, lt - 1, rnd); sort3ways(arr, gt, r, rnd); } private static <E> void swap(E[] arr, int i, int j) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static void main(String[] args) { int n = 1000000; Integer[] arr = ArrayGenerator.generateRandomArray(n, n); Integer[] arr2 = Arrays.copyOf(arr, arr.length); Integer[] arr3 = Arrays.copyOf(arr, arr.length); System.out.println("Random Array"); SortingHelper.sortTest("QuickSort", arr); SortingHelper.sortTest("QuickSort2Ways", arr2); SortingHelper.sortTest("QuickSort3Ways", arr3); System.out.println(); arr = ArrayGenerator.generateOrderedArray(n); arr2 = Arrays.copyOf(arr, arr.length); arr3 = Arrays.copyOf(arr, arr.length); System.out.println("Ordered Array"); SortingHelper.sortTest("QuickSort", arr); SortingHelper.sortTest("QuickSort2Ways", arr2); SortingHelper.sortTest("QuickSort3Ways", arr3); System.out.println(); arr = ArrayGenerator.generateRandomArray(n, 1); arr2 = Arrays.copyOf(arr, arr.length); arr3 = Arrays.copyOf(arr, arr.length); System.out.println("Same Value Array"); // SortingHelper.sortTest("QuickSort", arr); SortingHelper.sortTest("QuickSort2Ways", arr2); SortingHelper.sortTest("QuickSort3Ways", arr3); System.out.println(); } }
归并
复杂度为 nlogn,对完全有序的数组复杂度为 O(n)
import java.util.Arrays; public class MergeSort { private MergeSort() { } public static <E extends Comparable<E>> void sort(E[] arr) { sort(arr, 0, arr.length - 1); } private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) { if (l >= r) return; /* 考虑到l + r相加的时候r的值太大会溢出 * 比如 l = 3, r = 21。 * (l + r) / 2 = (21 + 3) / 2 = 24 / 2 = 12; * l + (r - l) / 2 = 3 + (21 - 3) / 2 = 3 + 18 / 2 = 3 + 9 = 12; */ int mid = l + (r - l) / 2; sort(arr, l, mid); sort(arr, mid + 1, r); if (arr[mid].compareTo(arr[mid + 1]) > 0) merge(arr, l, mid, r); } // 合并两个有序的区间 arr[l, mid] 和 arr[mid + 1, r] private static <E extends Comparable<E>> void merge( E[] arr, int l, int mid, int r ) { E[] temp = Arrays.copyOfRange(arr, l, r + 1); int i = l, j = mid + 1; // 每轮循环为 arr[k] 赋值 for (int k = l; k <= r; k++) { if (i > mid) { arr[k] = temp[j - l]; j++; } else if (j > r) { arr[k] = temp[i - l]; i++; } else if (temp[i - l].compareTo(temp[j - l]) <= 0) { arr[k] = temp[i - l]; i++; } else { arr[k] = temp[j - l]; j++; } } } public static void main(String[] args) { int n = 100000; Integer[] arr = ArrayGenerator.generateRandomArray(n, n); SortingHelper.sortTest("MergeSort", arr); } }
通过内存复用进行优化
import java.util.Arrays; public class MergeSort { private MergeSort() { } public static <E extends Comparable> void sort(E[] arr) { sort(arr, 0, arr.length - 1); } private static <E extends Comparable> void sort(E[] arr, int l, int r) { if (l >= r) return; int mid = l + (r - l) / 2; sort(arr, l, mid); sort(arr, mid + 1, r); if (arr[mid].compareTo(arr[mid + 1]) > 0) merge(arr, l, mid, r); } private static <E extends Comparable> void merge( E[] arr, int l, int mid, int r ) { E[] temp = Arrays.copyOfRange(arr, l, r + 1); int i = l, j = mid + 1; // 每轮循环为 arr[k] 赋值 for (int k = l; k <= r; k++) { if (i > mid) { arr[k] = temp[j - l]; j++; } else if (j > r) { arr[k] = temp[i - l]; i++; } else if (temp[i - l].compareTo(temp[j - l]) <= 0) { arr[k] = temp[i - l]; i++; } else { arr[k] = temp[j - l];
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。