冒泡排序#

算法复杂度： O(n^2) 稳定性：是稳定排序算法，相等的元素不会变换位置

1
package main
2
import "fmt"
3
func main() {
4
    var n int
5
    fmt.Scan(&n)
6
    arr := make([]int,n)
7
    for i:= range arr {
8
        fmt.Scan(&arr[i])
9
    }
10
    bubbleSort(arr)
11
    for i,v := range arr {
12
        if i > 0 {
13
            fmt.Print(" ")
14
        }
15
        fmt.Print(v)
16
    }
17

18
}
19
func bubbleSort(arr []int) {
20
    n := len(arr)
21
    for i:=0;i<n-1;i++ {
22
        for j:=0;j<n-1-i;j++ {
23
            if arr[j] > arr[j + 1] {
24
                arr[j],arr[j + 1] = arr[j + 1],arr[j]
25
            }
26
        }
27
    }
28
}

1
import java.util.Scanner;
2
public class Main {
3
    public static void main(String[] args) {
4
        Scanner sc = new Scanner(System.in);
5
        int n = sc.nextInt();
6
        int[] arr = new int[n];
7
        for(int i = 0;i<n;i++) {
8
            arr[i] = sc.nextInt();
9
        }
10
        bubbleSort(arr);
11
        for(int i = 0;i<n;i++) {
12
            System.out.print(arr[i] + " ");
13
        }
14

15
    }
16
    static void bubbleSort(int[] arr) {
17
        int n = arr.length;
18
        for(int i = 0;i<n - 1;i++) {
19
            for(int j = 0;j<n - 1 - i;j++) {
20
                int temp = arr[j];
21
                if(arr[j + 1] < arr[j]) {
22
                    arr[j] = arr[j + 1];
23
                    arr[j + 1] = temp;
24
                }
25
            }
26
        }
27
    }
28
}

快速排序#

时间复杂度#

平均时间复杂度： O(nlogn) 最坏时间复杂度： O(n^2) 在已经排序或者大部分已排序的情况下最好时间复杂度： O(nlogn)

空间复杂度#

是原地排序，只占用少量的额外空间，空间复杂度是O(logn)，主要是递归调用栈的空间

稳定性#

快速排序是不稳定排序。

采用分治策略排列元素，把数组分成两个子数组，递归排序，再合并。

分区的基本思想分区的目标：选择一个基准元素（pivot），将数组重新排列，使得：

分区思想#

基准左边的所有元素 <= 基准基准右边的所有元素 >= 基准基准本身位于最终的正确位置

1
package main
2

3
import "fmt"
4
func main() {
5
    var n int
6
    fmt.Scan(&n)
7
    arr := make([]int,n)
8
    for i:= range arr {
9
        fmt.Scan(&arr[i])
10
    }
11
    quickSort(arr,0,len(arr) - 1)
12
}
13
func quickSort(arr []int,low int,high int) {
14
    if low < high {
15
        pi := partition(arr,low,high)
16
        quickSort(arr,low,pi - 1)
17
        quickSort(arr,pi + 1,high)
18
    }
19
}
20
func partition(arr []int,low int,high int) int {
21
    pivot := arr[high]
22
    i := low - 1
23
    for j := low;j < high;j++ {
24
        if arr[j] <= pivot {
25
            i++
26
            arr[i],arr[j] = arr[j],arr[i]
27
        }
28
    }
29
    arr[i + 1],arr[high] = arr[high],arr[i + 1]
30
    return i + 1
31
}