当前位置：首页 > article >正文

选择排序冒泡排序 MySQL 架构

article 2024/12/27 4:09:21

1) 选择排序

思想：

1、遍历数组，选择找到最大值，记录最大值下标 maxindex，然后将最大值与最后一个值交换，

即 swap(vec[maxindex] , vec[n-1]);

2、在剩下的待排序数组中，重新找到最大值，重复第一步，swap(vec[maxindex] , vec[n-2]);

循环操作，直至数组排序完成。

#include<iostream>

using namespace std;

const int N = 1e4;

int num[N],n;

void Select_sort(){

    for(int i = 1; i < n; i++){//外层for控制找最大值的次数
    
        int index = 0;

        for(int j = 1; j <= n-i; j++){//找待排序元素中的最大值

            if(num[index] < num[j])  

                index = j;

        } 

        swap(num[index],num[n-i]);//交换

    }

}


int main(){

    cin>>n;

    for(int i = 0; i < n; i++){

        cin>>num[i];

    }

    Select_sort();

    for(int i = 0; i < n; i++)
    
        cout<<num[i]<<" ";

    return 0;

}

平均时间复杂度：O(n^2)

第一次排序时是 n 个元素，比较 n-1 次

第二次排序时是 n-1 个元素，比较 n-2 次

第 n-1 次排序时是 2 个元素，比较 1 次

第 n 次排序时是 1 个元素，比较 0 次

元素交换次数为 k ( k < n-1 次）

时间复杂度 = 比较次数 + 交换次数

故选择排序时间复杂度为 O( 1+2+3+...+n-1+k) = O(n*(n-1)/2+k) = O(n^2)

空间复杂度：O(1)

在原数组上操作，即使用了常数级空间O(1)

稳定性：

不稳定

实例：3 2 3 1 从小到大排序（选择最小的放前面）排序之后红色 3 在黑色 3 前面，所以不稳定。

2)冒泡排序

思想：

1、从左到右，相邻两数两两比较，若下标小的数大于下标大的数则交换，将最大的数放在数组的最后一位（即下标 n-1 的位置）

2、采用相同的方法，再次遍历数组，将第二大的数，放在数组倒数第二的位置（即 n-2 的位置），以此类推，直到数组有序。

3、优化：当数组在整个遍历过程中没有发生交换，说明待排序数组已经有序，此时可以直接结束排序过程（用 bool 类型变量做标记）。

#include<iostream>

using namespace std;

const int N = 1e4;

int num[N],n;

void Bubble_sort(){

    for(int i = 1; i < n; i++){
    
        bool flag = false;

        for(int j = 0; j < n-i; j++){

            if(num[j] > num[j+1])  {

                swap(num[j],num[j+1]);

                flag = true;

            }     

        } 

        if(!flag) return;

    }

}


int main(){

    cin>>n;

    for(int i = 0; i < n; i++){

        cin>>num[i];

    }

    Bubble_sort();

    for(int i = 0; i < n; i++)
    
        cout<<num[i]<<" ";

    return 0;

}

平均时间复杂度：O(n^2)

最好时间复杂度（有序情况）：O(n)

比较 n-1 次，交换 0 次，故最好时间复杂度为 O(n)

最坏时间复杂度（逆序情况）：O(n^2)

第一次排序时是 n 个元素，比较 n-1 次，交换 n-1 次

第二次排序时是 n-1 个元素，比较 n-2 次，交换 n-2 次

第 n-1 次排序时是 2个元素，比较 1 次，交换 1 次

第 n 次排序时是 1 个元素，比较 0 次，交换 0 次

故冒泡排序时间复杂度为 O((1+2+3...+n-1)*2) = O(n*(n-1)) = O(n^2)

空间复杂度：O(1)

在原数组上操作，即使用了常数级空间 O(1)

稳定性