数据结构算法之冒泡排序和选择排序

冒泡排序：相邻两个数比较，如果前面一个比后面一个数大，就进行交换

交换动画如下(动画是拷贝过来的)

冒泡排序.gif

void bubbleSort(int arr[], int len) {
    for (int i = 0; i < len - 1; ++i) {
        for (int j = 0; j < len - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

代码分析：
冒泡排序主要思想就是把最大的数往后排，每次都需要从零开始排序，排完之后就不需要考虑它了,所以是len-i-1,len-i相当于已经排好了的数在最后了，不需要考虑了

时间复杂度：当i=0的时候，j执行n-1次，当i=1的时候，j执行n-2次以此推理，当i=len-2次，j执行1次，所以一共执行了1+2+....+n-1次，也就是(n-1)*n/2次，所以时间复杂度是O(n^2)级别的

冒泡排序优化：主要思想，减少不必要的次数比较

• 第一种方法，添加标志位
  比如：9，1，2，3，4，5，6，7，只需要交换一次，再次遍历后发现，数组已经排序好，这时候就不需要再进行循环比较了

void optimizeBubbleSort1(int arr[], int len) {
    for (int i = 0; i < len - 1; ++i) {
        int flag=0;
        for (int j = 0; j < len - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                flag=1;
                std::swap(arr[j], arr[j + 1]);
            }
        }
        if(flag==0){
            break;
        }
    }
}

• 第二种方法：记录最后发生交换的位置，作为下一趟比较结束的位置
  比如，3，2，1，4，5，6。第一次循环后我们发现4，5，6三个已经排好序，也就是不需要再进行比较了，此时结束的位置放在第一次排好序的3这个位置就可以了

void optimizeBubbleSort2(int arr[], int len) {
    //记录上次遍历最后的一个位置
    int n = len;
    int newn = 0;//控制位置
    do {
        newn = 0;
        for (int i = 1; i < n; ++i) {
            if (arr[i - 1] > arr[i]) {
                std::swap(arr[i-1], arr[i]);
                //记录最后一次交换的位置
                newn = i;
            }
        }
        n = newn;
    } while (n > 0);
}

选择排序:首先循环遍历比较找到最小值的下标，然后将最小值和第一个位置的数进行交换

选择排序.gif

void selectSort(int arr[],int len){
    for (int i = 0; i < len; ++i) {
        int min=i;
        for (int j = i+1; j < len; ++j) {
            if(arr[min]>arr[j]){
                min=j;
            }
        }
        std::swap(arr[i],arr[min]);
    }
}

其时间复杂度也是O(n^2)，具体就不做分析，因为比较简单。

对选择排序和冒泡排序的执行时间比较

首先需要定义一个工具类，用于生成随机数，拷贝数据和执行耗时时间

#include <stdlib.h>
#include <android/log.h>
#include <time.h>
#include <assert.h>


#define TAG "TAG"
#define LOGE(...) __android_log_print(ANDROID_LOG_ERROR, TAG, __VA_ARGS__)

namespace ArrayUtils {
    //创建随机数
    int *create_random_array(int len, int low, int high) {
        int *arr = new int[len];

        for (int i = 0; i < len; ++i) {
            arr[i] = rand() % (high - low) + low;
        }

        return arr;
    }

    //拷贝数据
    int *copy_random_array(int *arr, int len) {
        int *copy_array = new int[len];
        memcpy(copy_array, arr, sizeof(int) * len);
        return copy_array;
    }
      //排序执行时间，void(*sort)(int *, int)，void表示返回参数，
     //*sort表示方法执行方法的别名，(int *, int)是因为我们的参数是(int arr[],int len)
    void sort_array(char *sortName, void(*sort)(int *, int), int *arr, int len) {
        size_t start_time = clock();
        sort(arr, len);
        size_t end_time = clock();
        // 计算算法的执行时间
        double time = static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC;
        LOGE("%s的执行时间：%lf", sortName, time);

        // 检测这个数组有没有拍好序
        for (int i = 0; i < len - 1; ++i) {
            assert(arr[i] <= arr[i + 1]);
        }
    }
}

测试

    int len = 20000;
    int *arr = ArrayUtils::create_random_array(len, 20, 10000);
    int *arr1 = ArrayUtils::copy_random_array(arr,len);
    ArrayUtils::sort_array("bubbleSort", bubbleSort, arr, len);
    ArrayUtils::sort_array("selectSort", selectSort, arr1, len);
    delete[](arr);
    delete[](arr1);