排序

文中图片均来自于网络
冒泡排序

冒泡排序
template <class T>
void bubbleSort(T arr[], int len) {
    for (int i = 0; i < len - 1; ++i) { //  n-1 步
        for (int j = 0; j < len - i - 1; ++j) { // n-1, n-2 ,n - 3, 1
            if (arr[j] > arr[j + 1]) {
                // 交换 一次交换是三次赋值
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

时间复杂度: O(n^2), 属于稳定排序

优化1 （优化外层循环）:设置交换的flog

template <class T>
void bubbleSort(T arr[], int len) {

    for (int i = 0; i < len - 1; ++i) { //  n-1 步
        bool change_flog = false;
        for (int j = 0; j < len - i - 1; ++j) { // n-1, n-2 ,n - 3, 1
            if (arr[j] > arr[j + 1]) {
                // 交换 一次交换是三次赋值
                std::swap(arr[j], arr[j + 1]);
                change_flog = true;
            }
        }
        if (!change_flog) {
            break;
        }
    }
}

优化2（优化内层循环）：记住最后一次交换发生的位置lastExchange

template <class T>
void bubbleSort(T arr[], int len) {
    int last_pos = 0;
    int k = len - 1;
    for (int i = 0; i < len - 1; ++i) { //  n-1 步
        bool change_flog = false;
        for (int j = 0; j < k; ++j) { // n-1, n-2 ,n - 3, 1
            if (arr[j] > arr[j + 1]) {
                // 交换 一次交换是三次赋值
                std::swap(arr[j], arr[j + 1]);
                change_flog = true;
                last_pos = j;
            }
        }
        k = last_pos;
        if (!change_flog) {
            break;
        }
    }
}

选择排序

选择排序
template <class T>
void selectSort(T 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;
            }
        }
        //一次交换
        swap(arr[i], arr[min]);
    }
}

时间复杂度: O(n^2）, 属于稳定排序

优化 : 一边最大，一边最小

template <class T>
void selectSort(T arr[], int len) {
    int left = 0;
    int right = len - 1;
    while (left < right) {
        int min = left;
        int max = right;
        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[min])
                min = i;
            if (arr[i] > arr[max])
                max = i;
        }
        //考虑修正的情况，最大值在最小位置，最小值在最大位置。
        swap(arr[max], arr[right]);

        if (min == right) {
            min = max;
        }
        swap(arr[min], arr[left]);
        left++;
        right--;
    }
}

插入排序

前身：

template <class T>
void insertSort(T arr[], int len) {
    for (int i = 1; i < len; ++i) {
        for (int j = i; j > 0 ; --j) {
            if(arr[j] < arr[j - 1]){
               swap(arr[j], arr[j - 1]);
            }else {
                break;
            }
        }
    }
}

时间复杂度:O(n^2)

优化：上面得排序代码交换位置很多，我们优化减少交换的次数。每一次先拿出当前位置作为临时值，然后在遍历和前一个数比较，如果前面一个数大于临时值，那么将当前位置的值赋值为前面一个数的值,反正则记录位置，跳出遍历，最后将那个记录位置赋值为记录的临时值即可。原理就像是扑克牌一样，找个合适的位置，然后插入。

插入排序
插入排序优化
template <class T>
void insertSort(T arr[], int len) {
    int j, i;
    for (i = 1; i < len; ++i) {// O(n)
        // 当前的位置
        int tmp = arr[i];
        for (j = i; j > 0; --j) {
            if(arr[j - 1] > tmp){
              arr[j] = arr[j - 1];
            }else {
                break;
            }
        }
        // 插入合适的位置
        arr[j] = tmp;
    }
}

优化之后的插入排序最好的情况（接近排好序的）时间复杂度是O(n)，这个是很强的。 属于稳定排序

希尔排序

我的理解希尔排序是一个优化的插入排序，插入排序在接近排好序的数据进行排序效率是非常高的，所以希尔排序主要就是进行将一个数据紊乱的数组通过插入排序给尽量的排好序。 属于不稳定排序。
思想：分治

希尔排序
template <class T>
void shellInsertSort(T arr[], int len) {
    int increment = len / 2;
    int i, j, k;
    while (increment >= 1) {
        for (i = 0; i < increment; ++i) {
            for (j = i + increment; j < len; j += increment) {
                int tmp = arr[j];
                for (k = j; k > i ; k -= increment) {
                    // 往后逻动
                    if(arr[k - increment] > tmp){
                        arr[k] = arr[k - increment];
                    }else{
                        break;
                    }
                }
                arr[k] = tmp;
            }
        }
        increment /= 2;
    }
}

如果一个组数据接近排好序的，那么用希尔排序的效率将会非常高。

归并排序

参考: https://www.cnblogs.com/chengxiao/p/6194356.html

归并排序采用分治的思想进行排序（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
如下图所示:

归并排序

归并排序合并:

归并排序合并

void merge(int arr[], int left, int mid, int right, int temp[]) {
    int i = left;//左序列指针
    int j = mid + 1;//右序列指针
    int t = 0;//临时数组指针
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[t] = arr[i];
            i++;
        } else {
            temp[t] = arr[j];
            j++;
        }
        t++;
    }
    while (i <= mid) {//将左边剩余元素填充进temp中
        temp[t] = arr[i];
        t++;
        i++;
    }
    while (j <= right) {//将右序列剩余元素填充进temp中
        temp[t] = arr[j];
        t++;
        j++;
    }
    t = 0;
    //将temp中的元素全部拷贝到原数组中
    while (left <= right) {
        arr[left] = temp[t];
        left++;
        t++;
    }
}

void mergeSort_(int arr[], int left, int right, int temp[]) {
    if (left < right) {
        int mid = (left + right) >> 1;
        mergeSort_(arr, left, mid, temp);//左边归并排序，使得左子序列有序
        mergeSort_(arr, mid + 1, right, temp);//右边归并排序，使得右子序列有序
        merge(arr, left, mid, right, temp);//将两个有序子数组合并操作
    }
}

void mergeSort(int arr[], int len) {
    int temp[len];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
    mergeSort_(arr, 0, len - 1, temp);
}

时间复杂度：O(N*logN),稳定排序

快速排序

参考: https://blog.csdn.net/MoreWindows/article/details/6684558

快速排

使用挖坑填数+分治法的思想。

比如上图所示的3 6 5 9 7 1 8 2 4

取区间第一个数位基准，初始的时候，i=0,j=8,temp=arr[i]=3,可以理解将arr的第0个位置拿出来，挖了个坑，然后从j开始从前找到一个比temp小的数，也就是2,这个时候j=7,将2填到i的位置，也就是0的位置,i++。这个时候j=7的就被挖了出来就空了，需要一个数填，就需要从i=1开始找一个比temp大的数填到j=7的位置，找到了数值填之后，在重复找数填。

代码如下：


int partition_(int s[], int l, int r) //返回调整后基准数的位置
{
    int i = l, j = r;
    int x = s[l]; //s[l]即s[i]就是第一个坑
    while (i < j) {
        // 从右向左找小于x的数来填s[i]
        while (i < j && s[j] >= x)
            j--;
        if (i < j) {
            s[i] = s[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑
            i++;
        }

        // 从左向右找大于或等于x的数来填s[j]
        while (i < j && s[i] < x)
            i++;
        if (i < j) {
            s[j] = s[i]; //将s[i]填到s[j]中，s[i]就形成了一个新的坑
            j--;
        }
    }
    //退出时，i等于j。将x填到这个坑中。
    s[i] = x;

    return i;
}

void quickSort_(int s[], int l, int r) {
    if (l >= r) {
        return;
    }
    int i = partition_(s, l, r);//先成挖坑填数法调整s[]
    quickSort_(s, l, i - 1); // 递归调用
    quickSort_(s, i + 1, r);
}

// 快速排序
void quickSort(int arr[], int len) {
    quickSort_(arr, 0, len - 1);
}

时间复杂度： O(N*logN)，不稳定排序

堆排序

  1. 构造初始堆。将给定无序序列构造成一个最大堆（一般升序采用最大堆，降序采用最小堆)。
  2. 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
第一步

第二步

#include <iostream>

/**
 * 调整大根堆
 * @param arr
 * @param index
 * @param len
 */
static void adjustHeap(int *array, int k, int len) {
    //是否到底
    while (k * 2 + 1 < len) {
        //默认最大值为左孩子
        int max = k * 2 + 1;
        //有右孩子并且大于左孩子
        if (max + 1 < len && array[max] < array[max + 1]) {
            max = max + 1;
        }
        if (array[k] > array[max]) {
            break;
        }
        //交换
        std::swap(array[k], array[max]);
        k = max;
    }
}


static void heapSoft(int *arr, int len) {
    //1.构建大顶堆
    // 从最后一个不是叶子节点的节点，开始调整为大根堆
    for (int i = len / 2 - 1; i >= 0; --i) {
        adjustHeap(arr, i, len);
    }
    //2. 第一个与最后一个交换,然后在调整为大根堆，但是不考略最后一个了
    for (int i = len - 1; i > 0; --i) {
        std::swap(arr[0], arr[i]);
        adjustHeap(arr, 0, i);//对第0个数据调整，最后一个不考略
    }
}

时间复杂度：O(nlogn) ,不稳定排序.
参考: https://www.cnblogs.com/chengxiao/p/6129630.html

本文图片均来自于网络。

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 八大经典排序算法原理及实现
    该系列文章主要是记录下自己暑假这段时间的学习笔记，暑期也在实习，抽空学了很多，每个方面的知识我都会另起一篇博客去记...
    Yanci516阅读 12,264评论 6赞 19
  • 常规排序算法总结
    概述 因为健忘，加上对各种排序算法理解不深刻，过段时间面对排序就蒙了。所以决定对我们常见的这几种排序算法进行统一总...
    清风之心阅读 717评论 0赞 1
  • （转）八大排序算法
    概述 排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部...
    蚁前阅读 5,214评论 0赞 52
  • 排序 29
    1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,270评论 0赞 2
  • 2017.6.5 周一
    忙碌的一天开始了，晚上下班还是很期待和孩子们的交流互动，儿子今天参与了升旗仪式，很为你感到高兴，还记得你知道...
    温温温温渔阅读 281评论 0赞 1