文章目录

• 零、概述
• 一、比较类算法
• • 1、 交换排序
  • • 1）冒泡排序
    • 2、快速排序
  • 2、插入排序
  • • 1）简单插入排序
    • 2）希尔排序
  • 3、选择排序
  • • 1）简单选择排序
    • 2）堆排序
  • 4、归并排序
  • • 1）二路归并排序
    • 2）多路归并排序
• 三、非比较类排序
• • 1、计数排序
  • 2、桶排序
  • 3、基数排序

零、概述

排序算法可以大致分为比较类和非比较类。就是排序的方法是通过元素之间的比较得来，还是通过引入其他策略来得到有序数组。

比较类分为交换、选择、插入、归并四种。
1、交换的思想就是通过比较两个元素之间的大小，满足一个规则就要交换两个元素之间的位置，以达到排序的目的。
2、选择的思想就是选择N次，每次选择的元素就是数组剩下元素的最大（小）值。这样没选择一次有序数组就多一个元素。
3、插入的思想就是将无序数组逐个插入到有序数组中的过程。
4、归并其实是分治的思想，即 使得子序列有序，再将子序列都合并在一起，成为完全有序。

• 交换：冒泡排序、快速排序。
• 选择：简单选择、堆排序。
• 插入：简单插入、希尔排序。
• 归并：二路归并、多路归并。

非比较类排序算法包括计数排序、桶排序、基数排序。这类算法一般不是通过数组中数字的直接比较来排序，而是通过一些分组等策略来加快排序。

一、比较类算法

1、 交换排序

1）冒泡排序

排序的过程像是吐泡泡一样，从数组的开始向后，两两之间比较，出现 Data[i + 1] < Data[ i ]，就要交换两个元素的位置。这样一次遍历之后最后的元素就是数组中最大的元素，第二次吐泡泡，就产生了第二大的元素…经过N次，整个数组就都有序了。

void bubbleSort(vector&Data)
{int size = Data.size();for(int i = 0;i < size; ++i){for(int j = 0;j < size - i - 1; ++j){if(Data[j] > Data[j + 1]) swap(Data[j],Data[j + 1]);}}
}

2、快速排序

快速排序的思想是选择一个元素A，比元素A小的放到元素A的左边，比元素A大的放到元素右边。这样元素A的位置就确定了。接着对元素A左边、右边的数组使用同样的办法。

void quickSort(vector&Data,int left,int right)
{if(left < right){int i = left;int j = right;int x = Data[i];while(i < j){while(i < j && x < Data[j]) --j;if(i < j) swap(Data[i], Data[j]);while(i < j && x > Data[i]) ++i;if(i < j) swap(Data[i],Data[j]);Data[i] = x;quickSort(Data,left,i - 1);quickSort(Data,i + 1, right);}}
}

2、插入排序

1）简单插入排序

第一个元素认为是有序序列，向后遍历，将元素加入有序序列。

void insertSort(vector& Data)
{for(int i = 1;iint x = Data[i];int index = i - 1;while(index >= 0  && Data[index] > x){Data[index + 1] = Data[index];index--;}Data[index + 1] = x;}
}

2）希尔排序

将数组分为K个系列，K个序列分别进行直接插入排序。再将K个序列变成K/2个序列，进行直接插入排序。最后就变成两个序列进行直接插入排序。

  void shellSort(vector& Data){int size = Data.size();for(int gap = size / 2;gap > 0; gap /= 2){for(int i = 0;ifor(int j = i + gap;j < size;j += gap){int k = Data[j];int temp = j - gap;while(temp >=0 && Data[temp] > k){Data[temp + gap] = Data[temp];temp -= gap;}Data[temp + gap] = k;}}}}

3、选择排序

1）简单选择排序

数组中遍历，每次遍历找到当前无序数组中最小（大）位置。

void selectSort(vector&Data)
{for(int i = 0;iint index = i;for(int j = i + 1;j < Data.size();++j){if(Data[index] > Data[j]) index = j;}swap(Data[index],Data[i]);}
}

2）堆排序

堆是利用堆这种数据结构来设计的算法，是一种选择排序，最好、最差、平均的时间复杂度均是O(nlogn).堆是具有以下特点的完全二叉树：根节点大于等于左右孩子节点的值，称为大根堆；根节点小于等于左右孩子节点的值，称为小根堆。
其思路是将数据元素设置为一个大（或者小）根堆，取出根结点，放在数组末尾，继续将数组前N-1个元素进行堆调整，再取出堆顶，此时的堆顶元素是N-1个元素中的最大值，放在数组倒数第二的位置上。一次执行上述过程。

void adjust(vector&Data,int len,int index)
{
while(index < len / 2)
{int left = index*2 + 1;int right = index*2 + 2;int max_value_index = index;if(left < len && Data[left] > Data[max_value_index]) max_value_index = left;if(right < len && Data[right] > Data[max_value_index]) max_value_index = right;if(max_value_index != index) swap(Data[max_value_index],Data[index]);index++;
}
}void heapSort(vector&Data,int size)
{for(int i = size / 2;i >= 0;--i){adjuest(Data,size,i);}for(int i = size - 1;i >= 1;--i){swap(Data[i],Data[0]);adjuest(Data,i,0);}
}

4、归并排序

1）二路归并排序

思路：不断的将数组分为两部分，直到分到两个元素；两个元素合并（将两个元素排序）；在四个元素合并…，直到将N/2个元素和N/2个元素合并。整个过程像是像是一个菱形一样。先将数组元素展开，再将元素合并。

void merge(vector&Data,int left,int mid,int right)
{vectorresult;int i = left;int j = mid + 1;while(i <= mid && j <= right){if(Data[i] > Data[j]) result.push_back(Data[j++]);else result.push_back(Data[i++]);}while(i <= mid) result.push_back(Data[i++]);while(j <= right) result.push_back(Data[j++]);for(int k = 0;k&Data,int left,int right)
{if(left < right){int mid = (left + right) / 2;mergeSort(Data,left,mid);mergeSort(Data,mid + 1,right);merge(Data,left,mid,right);}
}

2）多路归并排序

二路归并的思想是在将数组合并的时候，是两个子序列之间进行合并，而多路是将多个序列进行合并。

三、非比较类排序

非比较类排序算法都是稳定的。

1、计数排序

待排序数组A，计数排序的思想是创建一个数组B，将A中的值和数组B中下标对应起来。A中的值和数组B的下标相等的话，就将数组B的值+1。那么遍历数组B，从左至右，对应下标中数值大于0，就将下标值输入进结果数组。例如A = {2，5，2，4，3}，那么对应B = {0,0,2,1,1,1}，遍历数组B，依次将2个2、1个3、一个4、一个5输入结果数组。最坏时间复杂度是O(n+k)。最好时间复杂度是O（n+k）。其中k是桶的个数

void countSort(vector&Data)
{int max_value = INT_MIN;for(int i = 0;iif(Data[i] > max_value) max_value = Data[i];}vectorresult(max_value+1,0);for(int j = 0;jresult[Data[j]]++;}int index = 0;int count = 0;for(int i = 0;i < max_value;++i){index = result[i];if(index!=0){Data[count++] = i;}  }
}

2、桶排序

桶排序是在计数排序的基础上发展而来的。就是新建N个桶，把数组中的数放到对应的桶中。比如排序数字全是小于100的数字，新建10个桶，分别是数字十位上的数字，这样桶与桶之间是有大小关系的，这样只需要将桶内的数字排完序，最后将数组合并就是有序的数组了。桶排序的时间影响主要是桶内的排序，桶内排序的时间复杂度越小，就越快，但是就越费空间。最坏时间复杂度是O(n2)。最好是O（n）。

3、基数排序

先按照数字的个位数排序，再按照十位、百位…。新建10个桶，将个位、十位、百位数字相同的放在一起。最坏时间复杂度是O(n*d)，其中d表示要进行多少次关键字选择（就是个位、十位…），如果k远远小于n的话，也就是数据比较集中，基数排序是时间复杂度是线性的。最好时间复杂度是O（n+k）。空间复杂度是O（n+k），k表示桶的个数。