文章目录

排序算法比较
排序算法稳定性
选择排序
冒泡排序
插入排序
希尔排序
快速排序
归并排序
GitHub:https://github.com/AnJiaoDe/AlgorithmOfSort
欢迎分享、转载、联系、指正、批评、撕逼

排序算法比较

在这里插入图片描述
图片转载于https://blog.csdn.net/weixin_41190227/article/details/86600821

排序算法稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

选择排序

搞呆的，
从第1个数开始，与后面所有的数进行比较，选出最小的数排最前面。
从i=0开始，比较a[i]与a[i+1], 如果a[i]<a[i+1], a[i]与a[i+1]交换位置, i++

图解如下：

在这里插入图片描述

int sort_select(int arr[], int size) {
    int temp;
    int count_for = 0;
    for (int i = 0; i < size - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < size; j++) {
            count_for++;
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    return count_for;
}

测试代码：

int  main() {
    int arr[] = { 3,9,12 ,1,6,7 };
    //int size = sizeof(arr) / sizeof(int);
    int size = sizeof(arr) / sizeof(arr[0]);

    auto start = system_clock::now();

    int count_for = 0;
    count_for = sort_select(arr, size);
    //count_for=sort_bubbling(arr, size);
    //count_for = sort_bubbling_optimize(arr, size);

    auto end = system_clock::now();
    auto duration = duration_cast<microseconds>(end - start);
    //cout <<"for循环"<<count_for<< "次花费了"<< double(duration.count()) * microseconds::period::num / microseconds::period::den<< "秒" << endl;
    cout << "for循环" << count_for << "次花费了" << double(duration.count()) << "微秒" << endl;

    for (int i = 0; i < size; i++) {
        printf("%d\n", arr[i]);
    }
    system("pause");
    return 0;
}

用数组{ 3,9,12 ,1,6,7 }测试，得到count_for（for循环次数）为15

2层for循环，平均时间复杂度：O(n^2)

冒泡排序

从后往前，与前一个数进行比较，如果比自己大，那么交换位置。当然也可以从前往后。

图解如下：

2个for循环，平均时间复杂度为O(n^2)

int sort_bubbling2(int arr[], int size) {
    //下面计算的size永远等于1，数组做函数参数退化成指针，32位操作系统中，sizeof(任何指针变量)
    //永远=4
    //printf("size=%d\n", sizeof(arr) / sizeof(arr[0]));
    int temp;
    int count_for = 0;
    for (int i = 0; i < size - 1; i++) {
        for (int j = size - 1; j > i; j--) {
            count_for++;
            if (arr[j] < arr[j - 1]) {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
    }
    return count_for;
}

用数组{ 3,9,12 ,1,6,7 }测试，得到count_for（for循环次数）为15

2层for循环，平均时间复杂度：O(n^2)

优化：

如上图，当i=2时，也就是进行了3趟比较，就已经排好序了，通过第4趟比较，我们可以知道数组是否已经排好序，如果已经排好序，那么不再需要进行第5趟比较。

我们可以通过定义一个boolean变量在第4趟比较完后判断是否已经排好序，第4趟比较，flag是无法置为true的，因为第3趟比较已经排好序，第4趟比较不存在arr[j] < arr[j - 1]的情况，代码如下：

int sort_bubbling3(int arr[], int size) {
    int temp;
    boolean flag;
    int count_for = 0;
    for (int i = 0; i < size - 1; i++) {
        flag = false;
        for (int j = size - 1; j > i; j--) {
            count_for++;
            if (arr[j] < arr[j - 1]) {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                flag = true;
            }
        }
        if (!flag) break;
    }
    return count_for;
}

用数组{ 3,9,12 ,1,6,7 }测试，得到count_for（for循环次数）为14,循环次数有所减少

2层for循环，平均时间复杂度：O(n^2)

这么看起来冒泡排序还是优于选择排序的。

插入排序

从第2个数开始，与前面所有的数进行比较，将较小的数放前面。当与左边最靠近的数比较时，比左边的数大，说明左边的数都已经排好序，应结束该趟比较，继续下一趟比较。

图解如下：

在这里插入图片描述

int sort_insert(int arr[], int size) {
    int temp;
    int count_for = 0;
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j > 0; j--) {
            count_for++;
            if (arr[j] < arr[j - 1]) {
                temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }else {        
                break;
            }
        }
    }
    return count_for;
}

用数组{ 3,9,12 ,1,6,7 }测试，得到count_for（for循环次数）为11,

2层for循环，平均时间复杂度：O(n^2)

希尔排序

希尔开始采用分组的思想进行排序。

在要排序的一组数中，根据间隔分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将间隔缩小,并重复上述过程。直至间隔为1,此时数据序列基本有序,最后进行插入排序。

研究证明：gap=length;gap=gap/3+1;性能是最好的

图解如下：

在这里插入图片描述

int sort_sheer(int arr[], int size) {
    int gap = size;
    int temp;
    int count_for = 0;
    do {
        gap = gap / 3 + 1;
        for (int i = gap; i < size ; i+=gap) {
            for (int j = i - gap; j>=0; j -= gap) {
                count_for++;
                if (arr[j] > arr[j +gap]) {
                    temp = arr[j + gap];
                    arr[j + gap] = arr[j];
                    arr[j] = temp;
                }
                else {
                    break;
                }
            }
        }
    } while (gap > 1);
    return count_for;
}

用数组{ 3,9,12 ,1,6,7 }测试，得到count_for（for循环次数）为14,

2层for循环，平均时间复杂度：O(n^2)，do while里gap计算很快归1，可以不计入O(n)。

如果数据序列基本有序，使用插入排序会更加高效。

快速排序

分组的思想排序

先从数列中取出一个数作为key值；
将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
对左右两个小数列重复第二步，直至各区间只有1个数。

图解如下：

在这里插入图片描述

int separate(int arr[], int left, int right) {
    int key = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= key) {
            right--;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= key) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = key;
    return left;
}
void sort_quick(int arr[], int left, int right) {
    int median = 0;
    if (left < right) {
        median = separate(arr, left, right);
        sort_quick(arr, left, median - 1);
        sort_quick(arr, median + 1, right);
    }
}

用数组{ 3,9,12 ,1,6,7 }测试，

sort_quick(arr, 0, size - 1);

平均时间复杂度：O(N*logN)

归并排序

将数组拆分成多个数组，每个数组仅有一个元素，然后将多个数组合并成一个数组。
合并2个数组的称为2路归并，合并3个数组的称为3路归并，多路归并。

希尔排序、快速排序，平均时间复杂度均为O(N*logN)，但只有归并排序是稳定的。

2路归并图解如下：
拆分：

在这里插入图片描述

合并：

在这里插入图片描述

void merge(int src[], int des[], int left, int middle, int right) {
    int i = left;
    int j = middle + 1;
    int k = left;
    while ((i <= middle) && (j <= right)) {
        if (src[i] < src[j]) {
            des[k++] = src[i++];
        }
        else {
            des[k++] = src[j++];
        }
    }
    while (i <= middle) {
        des[k++] = src[i++];
    }
    while (j <= right) {
        des[k++] = src[j++];
    }
}
void sort_merge(int src[], int des[], int left, int right, int length) {
    if (left == right) {
        des[left] = src[left];
    }
    else {
        int middle = (left + right) / 2;
        int * array = (int*)malloc(sizeof(int)*length);
        if (array != NULL) {
            sort_merge(src, array, left, middle, length);
            sort_merge(src, array, middle + 1, right, length);
            merge(array, des, left, middle, right);
        }
        free(array);
    }
}

用数组{ 3,9,12 ,1,6,7 }测试，

sort_merge(arr, arr, 0, size - 1, size);

平均时间复杂度：O(N*logN)

总结：排序算法里比较高级的算法很多都利用了分组的思想

GitHub:https://github.com/AnJiaoDe/AlgorithmOfSort

欢迎分享、转载、联系、指正、批评、撕逼

Github:https://github.com/AnJiaoDe

简书：https://www.jianshu.com/u/b8159d455c69

CSDN：https://blog.csdn.net/confusing_awakening

ffmpeg入门教程:https://www.jianshu.com/p/042c7847bd8a

微信公众号

这里写图片描述

QQ群

这里写图片描述