讨论详情 - 椰程信奥训练中心 - ok.hn.cn

编程
c++里的3种常用排序算法
leesa LV 8 @ 2024-2-21 16:19:20

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 10;
int arr[N] = { 11, 33, 77, 99, 66, 55, 22, 44, 88, 66 };

int main() {
    // 选择排序
    // for (int i = 0; i < N; i++) {
    //     for (int j = i + 1; j < N; j++) {
    //         if(arr[i] > arr[j] )
    //         swap(arr[i] , arr[j]);
    //     }
    // }

    // 冒泡
    // for (int i = 0; i < N; i++) {
    //     for (int j = 0; j < N - 1 - i; j++) {
    //         if (arr[j] > arr[j + 1]) {
    //             swap(arr[j], arr[j+1]);
    //         }
    //     }
    // }

    // 插入排序
    for (int i = 1; i < N; i++) { // 默认第一张已经排好序
        // 遍历并比较一个无序数组元素与所有有序数组元素
        for (int j = i; j > 0; j--) {
            if (arr[j] < arr[j - 1]  ) {
                swap(arr[j - 1], arr[j]);
            }
        }
    }

    for(int x : arr)
        cout << x << " ";

    return 0;
}

symo LV 10 MOD @ 2024-2-21 18:03:02

插入排序

#include <iostream>
using namespace std;

const int n = 10;
int arr[n] = { 11, 22, 33, 66, 99, 88, 77, 44, 55, 22 };
int main() {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j;

        for (j = i - 1; j >= 0 ; j--) {
            if (arr[j] < key) break;
            arr[j + 1] = arr[j];
        }

        arr[j + 1] = key;
    }


    for(int x : arr) cout << x << " ";
    return 0;
}

代码优化

for (int i = 1; i < n; i++) {
int key = arr[i];
int j;
for (j = i - 1; j >= 0 && arr[j] > key; j--) {
        arr[j + 1] = arr[j];
    }

    arr[j + 1] = key;
}

使用 while 处理

for (int i = 1; i < n; i++) {
   int key = arr[i];
   int j = i - 1; 
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j]; 
        j = j - 1;
   } 
   arr[j + 1] = key;
}