算法与数据结构体系课程
什么是算法
解决问题的方法
五大特性
有限性
确定性
可行性
输入
输出
什么是数据结构
研究的是数据如何在计算机中进行组织和存储,使得我们可以高效的获取数据获取修改数据
排序算法
选择排序
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() {