1、冒泡排序

  • 原理

从第一个开始与后面的一个比较如果不相等就替换，一直比下去就会把最大的或者最小的比到最后一个元素，下一次比较的时候就把第二大或者第二小的放在倒数第二个，依次重复下去就实现排序。

  • 时间复杂度

冒泡排序最好的时间复杂度为O(n)

冒泡排序的最坏时间复杂度为O(n^2)

冒泡排序最好的时间复杂度为O(n)

  • 空间复杂度

排序过程中只是使用数组原本的空间进行排序，因此空间复杂度为O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Bubble_Sort(int arr[],int size)
{
    int i=0,k=0; 
    int temp = 0;
    for(i=0;i<size;i++)
    {
        for(k=0;k<size-i-1;k++)
        {
            if(arr[k]<=arr[k+1])    // 从大到小
            {
                temp = arr[k];       // 替换位置
                arr[k] = arr[k+1];
                arr[k+1] = temp;
            }
        }
    }
}

2、快速排序

  • 原理

选择一个数据为基准，将数组中的比他小的数据放一边，大的数据放在另外一边。

  • 时间复杂度

快速排序算法在分治法的思想下，原数列在每一轮被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止，平均情况下需要logn轮，因此快速排序算法的平均时间复杂度是O(nlogn)

在极端情况下，快速排序算法每一轮只确定基准元素的位置，时间复杂度为O(N^2)

  • 空间复杂度

快速排序算法排序过程中只是使用数组原本的空间进行排序，因此空间复杂度为O(1)

  • 稳定性

快速排序算法在排序过程中，可能使相同元素的前后顺序发生改变，所以快速排序是一种不稳定排序算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
    快速排序
    递归的思想实现的时候注意退出条件
*/
void Quick_Sort(int arr[],int left,int right)
{
    /*退出条件*/
    if(left>=right){
        return;
    }
    int r = right,l = left;
    int pot = arr[l];  //  把最左边的数据当成基准
    while(l<r)   
    {
        /*右边往左边一个个的判断*/
        while((l<r)&&(pot<=arr[r])){
            r--;
        }
        if(l<r){
            arr[l] = arr[r];
        }
        /*左边往右边判断*/
        while((l<r)&&(pot>=arr[l]))
        {
            l++;
        }
        if((l<r)){
            arr[r] = arr[l];
        }
        if(l>=r){
            arr[l] = pot;
        }

    }
    Quick_Sort(arr,left,r-1);
    Quick_Sort(arr,r+1,right);


}