浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程
時(shí)間復(fù)雜度
- what：評(píng)價(jià)算法好壞（讀big O）
- 計(jì)算方法是：要高階去低階
- 運(yùn)行時(shí)間不是指實(shí)際程序運(yùn)行的時(shí)間 而是程序執(zhí)行的操作數(shù)
- 運(yùn)行時(shí)間比較的角度是隨著時(shí)間的增大函數(shù)曲線的變化的幅度
空間復(fù)雜度
- what：評(píng)價(jià)算法好壞（讀big O）
- 計(jì)算方法是：要高階去低階
- O（1）：自己建幾個(gè)變量
- O（n）：自己建一個(gè)數(shù)組或者該數(shù)組是目標(biāo)數(shù)組的一半（忽略系數(shù)）
常見排序算法性能
| 算法 | 時(shí)間復(fù)雜度 | 空間復(fù)雜度 | 穩(wěn)定性 |
|---|---|---|---|
| 冒泡排序 | O(N^2) | O(1) | 穩(wěn)定 |
| 插入排序 | O(N^2) | O(1) | 穩(wěn)定 |
| 選擇排序 | O(N^2) | O(1) | 不穩(wěn)定 |
| 歸并排序 | O(nlogn) | O(n) | 穩(wěn)定 |
| 快速排序 | O(nlogn) | O(logn) | 不穩(wěn)定 |
| 堆排序 | O(nlogn) | O(1) | 不穩(wěn)定 |
0 BaseSort
package 常見排序算法.練習(xí);
import java.util.Arrays;
/**
* @Description:
* @Author: boolean
* @Date: 2019/11/17 18:14
*/
public abstract class BaseSort {
// for test
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
public static void swap(int[] arr, int i, int j) {
//其實(shí)就是交換
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public void testSort(BaseSort sort){
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
sort.sort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
sort.sort(arr);
printArray(arr);
}
protected abstract void sort(int[] arr);
}
1.冒泡排序（BubbleSort）
思想：
https://www.cnblogs.com/kkun/archive/2011/11/23/bubble_sort.html
代碼1
import java.util.Arrays;
/**
* Created by buer on 2018/8/13.
*/
//冒泡排序
public class BubbleSort {
/**
* 進(jìn)行冒泡函數(shù)
* @param arr
*/
public static void bubbleSort(int[] arr){
if (arr == null || arr.length < 2){
return;
}
for (int end = arr.length - 1; end > 0; end--){ //控制隊(duì)列尾部位置羔巢，不斷向前
for (int i = 0; i < end; i ++){ //從頭到尾兩兩比較
if (arr[i] > arr[i + 1]){
swap(arr, i, i+1);
}
}
}
}
/**
* 交換函數(shù)
*/
public static void swap( int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
//其實(shí)就是交換
//arr[i] = arr[i] ^ arr[j];
//arr[j] = arr[i] ^ arr[j];
//arr[i] = arr[i] ^ arr[j];
}
}
2.選擇排序（SelectSort）
思想：
- 1 首先在未排序序列中找到最衅械邸（大）元素丘薛，存放到排序序列的起始位置垛吗，
- 2 然后万皿，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最泻茄唷（大）元素抖誉，然后放到已排序序列的末尾任洞。
- 3 以此類推，直到所有元素均排序完畢花鹅。
代碼1
public class SelectSort extends BaseSort {
@Override
protected void sort(int[] arr) {
for (int i = 0; i < arr.length -1 ; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]){
min = j;
}
}
swap(arr, i, min);
}
}
@Test
public void test(){
BaseSort sort = new SelectSort();
sort.testSort(sort);
}
}
3.插入排序（InsertSort）
思想：
和打牌一樣,后來(lái)的牌與前面相比氧腰，如果前面的牌大，就將大的牌向后移動(dòng)
代碼：
import java.util.Arrays;
/**
* Created by buer on 2018/8/15.
*/
public class InsertSort extends BaseSort {
@Override
protected void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j --) {
swap(arr, j, j + 1);
}
}
}
@Test
public void test( ){
BaseSort sort = new InsertSort();
sort.testSort(sort);
}
}
4.歸并排序
思想：
https://www.cnblogs.com/chengxiao/p/6194356.html
- 1.按中間位置左右遞歸劃分模塊
- 2.申請(qǐng)一個(gè)輔助數(shù)組
- 2.比較兩個(gè)數(shù)組元素的大小刨肃，按小到大放進(jìn)輔助數(shù)組中
- 3.比較后剩余元素直接放在輔助數(shù)組后面
- 4.將輔助數(shù)組放進(jìn)原來(lái)的數(shù)組
代碼
import java.util.Arrays;
public class Code_05_MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1); //l r中點(diǎn) 位運(yùn)算
mergeSort(arr, l, mid); //左部分有序
mergeSort(arr, mid + 1, r); //有部分有序
merge(arr, l, mid, r);
}
public static void merge(int[] arr, int l, int m, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int p1 = l; //左部分第一個(gè)數(shù)
int p2 = m + 1; //有部分第一個(gè)數(shù)
while (p1 <= m && p2 <= r) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; //填的數(shù)字加1之前的數(shù)
}
//下面兩個(gè)循環(huán)只發(fā)生一個(gè)
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
}
}
5 快速排序
思想
- 1 找出基準(zhǔn)（選中間值）
- 2 移動(dòng)左邊數(shù)字直到數(shù)字大于基準(zhǔn)
- 3 移動(dòng)右邊數(shù)字直到數(shù)字小于基準(zhǔn)
- 4 交換左右數(shù)字(與基準(zhǔn)值相等的數(shù)可以到任何一邊)
- 5 左邊遞歸
- 6 右邊遞歸
public class QucikSort {
public static void quickSort(int[] arr, int left, int right){
if ( left >= right||arr == null || arr.length <= 1){
return;
}
int pivot = arr[left + ((right - left) >> 1)];
int i = left;
int j = right;
while (i <= j ){
while (arr[i] < pivot){
++i ;
}
while (arr[j] > pivot){
-- j ;
}
if (i < j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
++i;
--j;
} else if (i == j) {
++i;
}
}
quickSort(arr, left, j);
quickSort(arr,i, right);
}
}
tip
快速排序適合大數(shù)據(jù)排序古拴，小數(shù)據(jù)的話插入排序更為適合
6.堆排序
思想：
- 1.從右到左，從下到上創(chuàng)建大頂堆
- 2.將堆頂元素放到數(shù)組最后真友，調(diào)整大頂堆
圖例：
代碼：
public class HeapSort extends BaseSort {
@Override
protected void sort(int[] arr) {
//1.構(gòu)建大頂堆
for(int i=arr.length/2-1;i>=0;i--){
//從第一個(gè)非葉子結(jié)點(diǎn)從下至上黄痪，從右至左調(diào)整結(jié)構(gòu)
adjustHeap(arr,i,arr.length);
}
//2.調(diào)整堆結(jié)構(gòu)+交換堆頂元素與末尾元素
for(int j=arr.length-1;j>0;j--){
swap(arr,0,j);//將堆頂元素與末尾元素進(jìn)行交換
adjustHeap(arr,0,j);//重新對(duì)堆進(jìn)行調(diào)整
}
}
/**
* 調(diào)整大頂堆（僅是調(diào)整過(guò)程，建立在大頂堆已構(gòu)建的基礎(chǔ)上）
* @param arr
* @param i
* @param length
*/
public static void adjustHeap(int []arr,int i,int length){
int temp = arr[i];//先取出當(dāng)前元素i
for(int k=i*2+1;k<length;k=k*2+1){//從i結(jié)點(diǎn)的左子結(jié)點(diǎn)開始盔然，也就是2i+1處開始
if(k+1<length && arr[k]<arr[k+1]){//如果左子結(jié)點(diǎn)小于右子結(jié)點(diǎn)桅打，k指向右子結(jié)點(diǎn)
k++;
}
if(arr[k] >temp){//如果子節(jié)點(diǎn)大于父節(jié)點(diǎn)，將子節(jié)點(diǎn)值賦給父節(jié)點(diǎn)（不用進(jìn)行交換）
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;//將temp值放到最終的位置
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
BaseSort sort = new HeapSort();
sort.testSort(sort);
}
}
