1、排序分类

 

比较排序：冒泡排序、选择排序、插入排序、归并排序、堆排序、快速排序（时间复杂度O(nlogn)~O(n^2)）

非比较排序：计数排序、基数排序、桶排序（时间复杂度O(n)）

 

 

2、冒泡排序

        

       

方法：

1. 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

// 分类 -------------- 内部比较排序// 数据结构 ---------- 数组// 最差时间复杂度 ---- O(n^2)// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)// 平均时间复杂度 ---- O(n^2)// 所需辅助空间 ------ O(1)// 稳定性 ------------ 稳定// 冒泡排序int bubble(int *a, int length){    int i = 0, j = 0;    for(i; i < length-1; i++){  // 每次循环都将最大的元素推到最后        for(j = 0; j < length-1-i; j++)  // 尚未排序的部分        {            if (a[j+1]
      
       =，这样会变得不稳定)            {                int tmp = a[j+1];                a[j+1] = a[j];                a[j] = tmp;            }        }    }    return 0;}
      

        注：将最大的总是排在最后，两个循环的取值容易出现问题

 

 

3、冒泡算法改进：鸡尾酒算法（定向冒泡排序）

        

       

方法：

        区别于冒泡排序只是从低到高，鸡尾酒排序是先由底到高将最大数送到最后，再由高到低将最小数送到最前面，如此循环

// 分类 -------------- 内部比较排序// 数据结构 ---------- 数组// 最差时间复杂度 ---- O(n^2)// 最优时间复杂度 ---- 如果序列在一开始已经大部分排序过的话,会接近O(n)// 平均时间复杂度 ---- O(n^2)// 所需辅助空间 ------ O(1)// 稳定性 ------------ 稳定// 鸡尾酒算法int bubble_improve(int * a, int length){    int left = 0, right = length -1;    while(left
       
        a[i+1])            {                int tmp = a[i+1];                a[i+1] = a[i];                a[i] = tmp;            }        }            right--;        for(int j = right; j>left; j-- ){  // 反序遍历            if(a[j-1]>a[j]){                int tmp = a[j-1];                a[j-1] = a[j];                a[j] = tmp;            }        }            left++;        }        return 0;}
       

 

      注： 循环一个从正向一个从反向，一个加一个减，两头都要考虑；两个全局变量的增减是相反的

              在乱数序列的状态下，鸡尾酒排序与冒泡排序的效率都很差劲。

 

4、选择排序

        

        有一箱苹果，每次都在所有苹果中选出最大的一个，放在最后，接着又在剩下的苹果中选出最大的一个，放在当前的最后

 

        

方法：

        1.初始时在序列中找到最小元素，放到序列的起始位置作为已排序序列；

        2.然后，再从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

 

        与冒泡排序的区别：

        冒泡排序是依次交换两个相邻顺序不合法的元素位置；

        选择排序是遍历一次记住最小的元素的位置，最后仅需交换一次就可以放到合适的位置。

// 分类 -------------- 内部比较排序// 数据结构 ---------- 数组// 最差时间复杂度 ---- O(n^2)// 最优时间复杂度 ---- O(n^2)// 平均时间复杂度 ---- O(n^2)// 所需辅助空间 ------ O(1)// 稳定性 ------------ 不稳定void Swap(int A[], int i, int j){    int temp = A[i];    A[i] = A[j];    A[j] = temp;}// 选择排序（这里是每次选出最小的放在最前端）int select(int* a, int length){    int min = 0;    for(int i=0; i

     

        注：已经排序的序列和尚未排序的序列要区分开，循环条件也要区别开

                 选择排序是不稳定的排序算法，不稳定发生在最小元素与A[i]交换的时刻。

 

5、插入排序

        

        类似于抓扑克，手里每抓一个牌，就找到他该在的位置，大于他的牌往后挪出一个空位置，插入即可。

 

       

方法：

        对于未排序数据(右手抓到的牌)，在已排序序列(左手已经排好序的手牌)中从后向前扫描，找到相应位置并插入。

// 分类 ------------- 内部比较排序// 数据结构 ---------- 数组// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)// 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)// 平均时间复杂度 ---- O(n^2)// 所需辅助空间 ------ O(1)// 稳定性 ------------ 稳定// 插入排序int insert(int a[], int n){    for(int i = 0; i < n; i++){        int get = a[i];  // 手里抓的牌        int j = i-1;  // 要和已经抓的牌比大小        while (j >= 0 && a[j] > get)  // 比抓到的牌大的，都向后挪一个位置        {            a[j+1] = a[j];            j--;        }        a[j+1] = get;  // 将抓到的牌放在该放的位置上啦    }    return 0;}

     注：模拟左右手抓牌的方式，左边有序，右边抓新牌，左手要空出一个合适的位置右手的牌直接插入即可

               如果需要排序的数据量很小，比如量级小于千，那么插入排序还是一个不错的选择。

 

 

6、插入排序的改进--二分插入排序

 

       

方法：

        先跟序列最中间的那个元素比较，如果比最中间的这个元素小，则插入位置在它的左边，否则在它的右边。以当前最中间位置为分割点，如果在左边，则当前最中间位置是待搜索子序列的终点，如果在右边，右边邻接的元素将是待搜索子序列的起点。按照这种原则，继续寻找下一个中间位置，并继续这种过程，直到找到合适的插入位置为止。

 

// 分类 -------------- 内部比较排序// 数据结构 ---------- 数组// 最差时间复杂度 ---- O(n^2)// 最优时间复杂度 ---- O(nlogn)// 平均时间复杂度 ---- O(n^2)// 所需辅助空间 ------ O(1)// 稳定性 ------------ 稳定// 二分插入排序void binary_insert(int a[], int n){       int i = 1;    while(i
          
           = head; j--){            a[j+1] = a[j];        }        a[head] =get;  // 将抓到的牌放在该放的位置上啦        i++;    }}
          

        注：每次二分查找都值针对已排序部分，注意循环条件。右手抓的牌要先用一个变量保存，因为之后会被替代掉。

             所当以元素初始序列已经接近升序时，直接插入排序比二分插入排序比较次数少。

 

 

7、插入排序高效改进--希尔排序

 

        

方法：

         先将整个待排元素序列切割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

 

// 分类 -------------- 内部比较排序// 数据结构 ---------- 数组// 最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)// 最优时间复杂度 ---- O(n)// 平均时间复杂度 ---- 根据步长序列的不同而不同。// 所需辅助空间 ------ O(1)// 稳定性 ------------ 不稳定// 希尔排序(重点：确定步长)void shell(int a[], int n){    int k = 2;    int step = n/k;  // 步长为一半    while(step >= 1){        for(int i = step; i < n; i++){  // 插入排序每次走1，希尔排序每次走step            int get = a[i];            int j = i - step;            while(j>=0 && get

        注：重点在于步长，与直接插入排序的区别就只是，直接插入每次移动一个，希尔排序是逐步长移动，用step代替逐增的1即可.

              希尔排序是不稳定的排序算法，虽然一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的   元素可能在各自的插入排序中移动，最后其稳定性就会被打乱。

 

 

8、归并排序

 

       

方法：

        归并排序的实现分为递归实现与非递归(迭代)实现

        递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。

        非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，直到归并了整个数组。

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

// 分类 -------------- 内部比较排序// 数据结构 ---------- 数组// 最差时间复杂度 ---- O(nlogn)// 最优时间复杂度 ---- O(nlogn)// 平均时间复杂度 ---- O(nlogn)// 所需辅助空间 ------ O(n)// 稳定性 ------------ 稳定// 归并排序void merge(int a[], int left, int mid, int right){    int length = right - left + 1;    int *tmp = new int[length];  // 新建辅助数组    int i = left, j = mid + 1;  // 两边的起始位置    int position = 0;  // 当前所在位置    while(i<=mid && j<=right){  // 将两个数组中比较小的放入tmp        tmp[position++] = a[i]<=a[j] ? a[i++] : a[j++];    }    while (i<=mid)  // 此时游标的数字已将全部在tmp中了，只需将左边全部放入    {        tmp[position++] = a[i++];    }    while(j<=right){        tmp[position++] = a[j++];    }    for(int k = 0; k < length; k++){        a[left++] = tmp[k];  // 要注意将辅助数组中的内容填入当前数组哦    }} // 归并递归(自顶而下)void mergeSortRecursion(int a[], int left, int right){    if(left == right)        return ;  // 递归结束的条件要加，否则栈溢出    int mid = (left + right)/2;    mergeSortRecursion(a, left, mid);    mergeSortRecursion(a, mid+1, right);    merge(a, left, mid, right);} // 归并迭代（自底向上）void mergeSortIteration(int a[], int n){    int left, mid, right;    for (int i = 1; i < n; i *= 2)  // 先两个两个归并，再四个四个归并    {        left = 0;        while(left + i < n){            mid = left + i -1;            right  = mid + i < n ? mid +i : n-1;            merge(a, left, mid, right);            left = right + 1;        }    }}

 

        注：最重要的是归并这个函数，new一个数组来存放临时排序结果，再将其赋值给原数组

            递归中一定要注意结束条件，其余实现左右自我调用即可

            迭代就是先两两排序，再四四排序，如此循环，要注意判断之后是否有字数组，将数组索引适当前移即可

 

 

9、堆排序

 

       

方法:

        1、节点下滤：将当前节点和左右孩子比较，若小于左右孩子，则将左右孩子中较大者上滤，自己下滤 到空位，再进行下一次节点下滤

        2、建堆：通过从最后一个有孩子的节点开始遍历，节点下滤 构成最大子堆，节点减1，依次网上遍历，直至构成最大堆

        3、算法：将堆首元素与堆尾元素交换，堆的规模减1，再从堆顶元素开始节点下滤 构成一个新的最大堆，再重复堆首位交换，规模减1，下滤为最大堆的过程。

// 分类 -------------- 内部比较排序// 数据结构 ---------- 数组// 最差时间复杂度 ---- O(nlogn)// 最优时间复杂度 ---- O(nlogn)// 平均时间复杂度 ---- O(nlogn)// 所需辅助空间 ------ O(1)// 稳定性 ------------ 不稳定// 归并排序void merge(int a[], int left, int mid, int right){    int length = right - left + 1;    int *tmp = new int[length];  // 新建辅助数组    int i = left, j = mid + 1;  // 两边的起始位置    int position = 0;  // 当前所在位置    while(i<=mid && j<=right){  // 将两个数组中比较小的放入tmp        tmp[position++] = a[i]<=a[j] ? a[i++] : a[j++];    }    while (i<=mid)  // 此时游标的数字已将全部在tmp中了，只需将左边全部放入    {        tmp[position++] = a[i++];    }    while(j<=right){        tmp[position++] = a[j++];    }    for(int k = 0; k < length; k++){        a[left++] = tmp[k];  // 要注意将辅助数组中的内容填入当前数组哦    }}// 归并递归(自顶而下)void mergeSortRecursion(int a[], int left, int right){    if(left == right)        return ;  // 递归结束的条件要加，否则栈溢出    int mid = (left + right)/2;    mergeSortRecursion(a, left, mid);    mergeSortRecursion(a, mid+1, right);    merge(a, left, mid, right);}// 归并迭代（自底向上）void mergeSortIteration(int a[], int n){    int left, mid, right;    for (int i = 1; i < n; i *= 2)  // 先两个两个归并，再四个四个归并    {        left = 0;        while(left + i < n){            mid = left + i -1;            right  = mid + i < n ? mid +i : n-1;            merge(a, left, mid, right);            left = right + 1;        }    }}

 

 

   

    注：算法的关键就是节点下滤和递归

            一定要注意size是比最大下标多1，下标从0开始的

            

 

10、快速排序

 

        

         哨兵i，j都向中间移动，以最左边的数为基准数，因此哨兵j先向左移动，j碰到比基准小的数的话就停止，并将当前的值赋给i所在的地方。此时i开始向右移动，碰到比基准大的值就停止，将他换到j的位置，换成j移动，如此循环直至两个哨兵相遇，将该位置的值设置成标准。至此标准左边的值都比标准小，右边的值都大，这就完成了一轮的快排。

 

       

方法：

        1、从序列中挑出一个元素，作为基准，

        2、将比基准小的元素放在基准前面，比基准大的元素放在基准后面。减小分区的规模，递归进行操作，直至分区的大小为0或1。

// 分类 ------------ 内部比较排序// 数据结构 --------- 数组// 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)// 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)// 平均时间复杂度 ---- O(nlogn)// 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)// 稳定性 ---------- 不稳定// 快排int partition(int a[], int left, int right){    int standard = a[left];    while(left < right){        while((left < right) && standard <= a[right]){  // 以左边为基准，所以右边的哨兵先移动            right--;        }        a[left] = a[right];  // 如果右边的数比标准还小，移到标准左边        while ((left < right) && standard >= a[left]){  // 左边的哨兵向右移动，碰到比标准小的就向左移一位            left++;         }        a[right] = a[left];  // 如果左边的数比标准还大，将该数移到标准右边    }    a[left] = standard;  // 最后将标准放在中间    return left;}void quick_sort(int a[], int left, int right){    if(left >= right) return;   // 退出条件很重要    int middle = partition(a, left, right);    quick_sort(a, 0, middle);  // 递归    quick_sort(a, middle+1, right);}

注：关于递归，一定要先写退出条件。先画图，理解原理了实现起来就比较简单。

 

个人博客地址：https://huahua462.github.io/