1.概况
- 选择排序、快速排序、希尔排序、堆排序
不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法 - 排序算法主要关注的 1.边界条件 2.交换时机 3.数据规模 4.终止条件
选择/插入/冒泡排序算法 等时间复杂度都是O(N2)- 选择排序没有提前终止循环的条件，一般都比插入排序更加慢。在近乎有序的情况下，虽然都不用做交换操作，但是多了比较的时间
- 选择排序
不稳定排序序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。 - 接下来再介绍几款时间复杂度为O(N)的算法。 桶排序 计数排序 基数排序
2.选择排序
template <typename T>
void selectsort(T arr[], int n)
{
for(int i = 0 ;i < n ; i++ ){
int minindex = i ;
for( int j = i+1 ; j < n ; j++){
if(arr[minindex] > arr[j]){
minindex = j ;
}
if( minindex != i ){
swap(arr[i],arr[minindex]);
}
}
return ;
}
3.冒泡排序
template <typename T>
void buddlesort(T arr[] , int n){
int flag = 0; //设定标志，如果第一次循环比较时没有发生交换，则说明数组是升序排序，不用排序，提前结束循环。
for(int i = 0; i < n ;i++){
for(int j = 0 ;j < n-i-1 ; j++){ //内层循环控制每次循环里比较的次数。
if(arr[j] > arr[j+1]){ // 这里有j+1 故上面循环到n-i-1
swap(arr[j],arr[j+1]);
flag =1 ;
}
}
if(flag == 0 ){ //没有交换说明有序，提前结束
break;
}
}
return ;
}
4.插入排序
稳定排序 插入排序在近乎有序的数据时候，可能退化成O(n)时间复杂度
template <typename T>
void insertsort(T arr[] , int n){
for(int i = 1 ; i < n ; i++){ //从第二个元素开始，1个元素默认就是有序的
T e = arr[i];
for(int j = i ; j > 0 ; j--){
if( e < arr[j-1]){
arr[j] = arr[j-1]
}else{
break;
}
}
arr[i] = e;
}
/*
for(int i = 1 ; i < n ; i++){ //从第二个元素开始，1个元素默认就是有序的
T e = arr[i];
int j; // j保存元素e应该插入的位置
for (j = i; j > 0 && arr[j-1] > e; j--)
arr[j] = arr[j-1];
arr[j] = e;
}
*/
return ;
}
5.希尔排序
不稳定排序 大于O(NlogN) 小于O(N2)
template<typename T>
void shellSort(T arr[], int n){
int h = 1;
while( h < n/3 )
h = 3 * h + 1;
// 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
while( h >= 1 ){
for( int i = h ; i < n ; i ++ ){
// 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
T e = arr[i];
int j;
for( j = i ; j >= h && e < arr[j-h] ; j -= h )
arr[j] = arr[j-h];
arr[j] = e;
}
h /= 3;
}
return ;
/*
for (gap = n / 2; gap > 0; gap /= 2)
for (i = gap; i < n; i++)
for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
Swap(a[j], a[j + gap]);
*/
}
6.归并排序
NlogN算法 需要开辟同样大小的临时空间
template <typename T>
void mergeSort(T arr[], int n ){
__mergeSort(arr,0 , n-1)
}
//用递归的方式 自顶向下
template <typename T>
void __mergeSort(T arr[] , int l ,int r){
if(l >= r){
return;
}
//优化二 在数据比较少，数据近乎有序的情况下，选择插入排序处理一下
/*
if(r - l <= 15 ){
insertSort(arr, l, r );
return ;
}
*/
int mid = l+(r - l )/2 ;//避免溢出
__mergeSort(arr, l ,mid);
__mergeSort(arr,mid+1 ,r);
//优化一 避免不用归并的情况
if(arr[mid] > arr[mid+1])
__merge(arr,l ,mid ,r);
}
//用循环的模式 自底向上
template <typename T>
void mergeSortBU( T arr[], int n ){
for(int sz = 1 ; sz <= n; sz += sz){
for(int i = 0 ; i +sz < n ; i += (sz+sz)){
//对arr[i...i+sz-1] 和arr[i+sz , i+sz+sz-1] 进行归并
__merge(arr,i ,i+sz-1 ,min(i+sz+sz-1 ,n-1));
}
}
}
//归并排序
template <typename T>
void __merge(T arr[], int l ,int mid , int r){
T temp[r-l+1] = {0};
for(int i = l ; i <= r; i++){
temp[i-l] = arr[i];
}
int i = l; j = mid+1 ;
for( int k = l; k <= r; k++){
if(i > mid ){ //判断前面是否超限
arr[k] = temp[j-l];
j++;
}else if(j > r ){
arr[k] = temp[i-l];
i++;
}
if(temp[i-l] < temp[j-l]){
arr[k] = temp[i-l];
i++;
}else{
arr[k] = temp[j-l];
j++;
}
}
}
7.快速排序
template <typename T>
void quickSort(T arr[], int n ){
__quickSort(arr, 0 ,n-1)
}
template <typename T>
void __quickSort(T arr[] , int l ,int r){
if(l >= r){
return ;
}
//优化二
/*
if(r - l <= 15 ){
insertSort(arr, l, r );
return ;
}
*/
int p = __partition(arr,l ,r);
__quickSort(arr, l ,p-1);
__quickSort(arr, p, r);
}
template <typename T>
//返回p ，分成两组 使得arr[l...p-1] < arr[p] ;arr[p+1...r] > arr[p]
int __partition(T arr[], int l ,int r){
swap( arr[l] , arr[rand()%(r-l+1)+l] );
//优化一 近乎有序的话，我们标定点最好随机选择
T temp = arr[l];
//使得arr[l+1...j] < temp ;arr[j+1...r] > temp
int j = l ;
for(int i = l+1 ; i <= r ; i++){
if(arr[i] < temp ){
swap (arr[j+1] ,arr[i]); // 把这个小于temp的值跟 原来大于temp的第一个数交易，同时j++就相当于重新分组
j++;
}
}
swap(arr[l] , arr[i]);
return j ;
}
三路快排(分为三组)针对有大量重复有奇效
(双路快排分为两组 小于等于一组，小于等于一组)
template <typename T>
void __quickSortWays3(T arr[] , int l ,int r){
if(l >= r){
return ;
}
//优化二
/*
if(r - l <= 15 ){
insertSort(arr, l, r );
return ;
}
*/
swap(arr[l] , arr[rand()%(r-l+1)+l]);
T temp = arr[l];
int lt = l ; //arr[l...lt] < temp
int gt = r +1 ; //arr[gt...r] > temp
int i = l +1;//arr[lt+1...i] = temp
while(i < gt ){
if(arr[i] > temp ){
swap(arr[i] , arr[gt-1]) ; //这个地方gt-1 交换过去 i就不能自增了
gt -- ;
}else if( arr[i] < temp ){
swap(arr[i] , arr[lt+1]);
lt ++ ;
i ++ ;
}else{
i++;
}
}
swap(arr[l] , arr[lt]);
__quickSortWays3(arr, l ,lt-1);
__quickSortWays3(arr, gt ,r );
}
8.桶排序
桶排序的时间复杂度为什么是O(n)呢？我们一块儿来分析一下。
如果要排序的数据有n个，我们把它们均匀地划分到m个桶内，每个桶里就有k=n/m个元素。每个桶内部使用快速排序，时间复杂度为O(k * logk)。
m个桶排序的时间复杂度就是O(m * k * logk)，因为k=n/m，所以整个桶排序的时间复杂度就是O(n*log(n/m))。
当桶的个数m接近数据个数n时，log(n/m)就是一个非常小的常量，这个时候桶排序的时间复杂度接近O(n)。
桶排序看起来很优秀，那它是不是可以替代我们之前讲的排序算法呢？
答案当然是否定的。为了让你轻松理解桶排序的核心思想，我刚才做了很多假设。实际上，桶排序对要排序数据的要求是非常苛刻的。
首先，要排序的数据需要很容易就能划分成m个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，
那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为O(nlogn)的排序算法了。
桶排序比较适合用在外部排序中。
所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
比如说我们有10GB的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百MB，
没办法一次性把10GB的数据都加载到内存中。这个时候该怎么办呢？
现在我来讲一下，如何借助桶排序的处理思想来解决这个问题。
我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是1元，最大是10万元。
我们将所有订单根据金额划分到100个桶里，第一个桶我们存储金额在1元到1000元之内的订单，第二桶存储金额在1001元到2000元之内的订单，
以此类推。每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02…99）。
理想的情况下，如果订单金额在1到10万之间均匀分布，那订单会被均匀划分到100个文件中，每个小文件中存储大约100MB的订单数据，
们就可以将这100个小文件依次放到内存中，用快排来排序。等所有文件都排好序之后，我们只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，
并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。
不过，你可能也发现了，订单按照金额在1元到10万元之间并不一定是均匀分布的 ，所以10GB订单数据是无法均匀地被划分到100个文件中的。
有可能某个金额区间的数据特别多，划分之后对应的文件就会很大，没法一次性读入内存。这又该怎么办呢？
针对这些划分之后还是比较大的文件，我们可以继续划分，比如，订单金额在1元到1000元之间的比较多，
我们就将这个区间继续划分为10个小区间，1元到100元，101元到200元，201元到300元…901元到1000元。
如果划分之后，101元到200元之间的订单还是太多，无法一次性读入内存，那就继续再划分，直到所有的文件都能读入内存为止。
9.计数排序
// 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。
public void countingSort(int[] a, int n) {
if (n <= 1) return;
// 查找数组中数据的范围
int max = a[0];
for (int i = 1; i < n; ++i) {
if (max < a[i]) {
max = a[i];
}
}
int[] c = new int[max + 1]; // 申请一个计数数组c，下标大小[0,max]
for (int i = 0; i <= max; ++i) {
c[i] = 0;
}
// 计算每个元素的个数，放入c中
for (int i = 0; i < n; ++i) {
c[a[i]]++;
}
// 依次累加
for (int i = 1; i <= max; ++i) {
c[i] = c[i-1] + c[i];
}
// 临时数组r，存储排序之后的结果
int[] r = new int[n];
// 计算排序的关键步骤，有点难理解
//这里从后往前计算
for (int i = n - 1; i >= 0; --i) {
int index = c[a[i]]-1; //得到索引
r[index] = a[i]; //存放原始的数据
c[a[i]]--; //个数减去一
}
// 将结果拷贝给a数组
for (int i = 0; i < n; ++i) {
a[i] = r[i];
}
}
10.基数排序
我们再来看这样一个排序问题。
假设我们有10万个手机号码，希望将这10万个手机号码从小到大排序，你有什么比较快速的排序方法呢？
我们之前讲的快排，时间复杂度可以做到O(nlogn)，还有更高效的排序算法吗？桶排序、计数排序能派上用场吗？
手机号码有11位，范围太大，显然不适合用这两种排序算法。针对这个排序问题，有没有时间复杂度是O(n)的算法呢？
现在我就来介绍一种新的排序算法，基数排序。
刚刚这个问题里有这样的规律：假设要比较两个手机号码a，b的大小，如果在前面几位中，a手机号码已经比b手机号码大了，那后面的几位就不用看了。
借助稳定排序算法，这里有一个巧妙的实现思路。还记得我们第11节中，在阐述排序算法的稳定性的时候举的订单的例子吗？
我们这里也可以借助相同的处理思路，先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，
以此类推，最后按照第一位重新排序。经过11次排序之后，手机号码就都有序了。
扫描关注我
（转载本站文章请注明作者和出处 Undefined）