基础排序算法

这里对基础排序算法做个整理,如下:
1.Insertion Sort
2.Bubble Sort
3.Bucket Sort
4.Selection Sort
5.Quick Sort
6.STL: Priority_Queue
7.Heap Sort
8.Merge Sort
9.Shell Sort

1.插入排序 Insertion Sort

原理

(从小到大排序)

1.将数都放在a[]数组里,遍历a[],令临时变量 key 为当前遍历到的数 a[i];

2.为了将 key 放到正确的位置,需将 key 与 a[i] 前面的数进行比较,若 key < a[j],需把比 key 大的数往后移一位,即 a[j+1] = a[j];
直到找到 a[j],满足 key < a[j];
并将 key 放在 a[j] 的后面,即令 a[j+1] = key。

时间复杂度 O(n2)

代码实现

void InsertionSort(int *a, int len){
    for (int i=1; i<len; i++){
        int key = a[i];
        int j = i - 1;
        while (j>=0 && a[j]>key){ 
        //将比key大的数都往后移一位,直到找到比key小的数        
        a[j+1] = a[j];
        j--;
    }
        a[j+1] = key;          
        //跳出while即找到了比key小的数a[j],那么将key插入到a[j]后面
    }
}

2.冒泡排序 Bubble Sort

原理

外层循环控制循环次数,内层循环比较相邻两位数;

时间复杂度 O(n2)

代码实现

(从小到大)

void BubbleSort(int *a,int len){        
    for(int i=0;i<len;i++){
        for(int j=0;j<len-1;j++){            
            if(a[j]>a[j+1]){
                int temp=a[j];                
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
}

3.桶排 Bucket Sort

原理

1.不同于别的排序算法,桶排是基于数组下标实现的排序;最大的区别在于存储数组中的数据时,我们用数组下标存入,用数组的值记录数量;

2.举个栗子:
我们需读入数组的数据为,5,1,2,1,5,2,3
存储时我们将第一个数字 5,存到 a[5]++; 以此类推
输出时,for(int i=Min_Number;i<=Max_Number;i++) 输出所存储的数;

代码实现

(从小到大)

void BucketSort(int len){
    for(int i=0;i<len;i++){
        cin>>x;
        a[x]++;        //用数组下标存数据,用数组的值统计个数
        if(x<Min_Number) Min_Number=x;
        if(x>Max_Number) Max_Number=x;
    }
    for(int i=Min_Number;i<=Max_Number;i++){
        if(!a[i]){
            for(int j=1;j<=a[i];j++) cout<<j<<" ";                   
        }
    }
}

注意

由桶排的原理的原理可知,桶排适用于数据范围小,而且有较多重复数据的数组排序;对于数据范围大的排序,还需离散化;

4.选择排序 Selection Sort

原理

(从大到小)

1.在每一次外层循环中,先假设 a[i] 为最大的数 a[Min];
2.比较 a[Max] 和 a[j],找到未排序的数列中最大的数,将它和第 i 位上的数进行交换;

时间复杂度 O(n2)

代码实现

void Selection_Sort(int *a){
    for(int i=0;i<len;i++){
        int Max = i;
        int j;
        for(j=i+1;j<len;j++){
            if(a[j]>a[Max])
                Max=j;      
        }
        if(Max!=i)
            Swap(a[i], a[j]);
    }
}

5.快速排序 Quick Sort

原理

1.快排基于分治的思想,先找到中间的数a[mid],将比a[mid]大的数和比a[mid]小的数进行交换;
2.二分区间,重复上述过程;

时间复杂度 O(nlogn)

代码实现

void Quicksort(int l,int r){
    int i=l,j=r,mid=a[(l+r)/2];    
    while(i<=j){
        while(a[i]>mid) i++;
        while(a[j]<mid) j--;
        if(i<=j){
            swap(a[i],a[j]);
            i++,j--;
        }    
    }
    if(i<r) Quicksort(i,r);
    if(j>l) Quicksort(l,j);
}

也可以直接使用 STL 里的 sort()

    #include <algorithm>                //头文件                   
    int a[n];
    sort(a,a+n);                    //默认从小到大            

注意:
1.sort默认从a[0]开始排序,以a[n-1]结尾,n为长度;
2.char数组,double数组,longlong数组等,也可以使用sort排序;

6.优先队列 Priority_Queue (STL)

原理

Priority_Queue 同样属于STL库中,是一种特殊的queue.

用法

#include <queue>
priority_queue <int> q; //普通优先级队列,默认从大到小排序;
priority_queue <int, vector<int>, less<int> > q; //自定义从小到大排序;

注:支持所有queue操作;

7.堆排 Heap Sort

原理 (基于堆操作和数组模拟)

根据堆的相关原理可知,建好堆之后,堆中的第0个数据是堆中最小的数。
取出这个数再执行堆删除。这样堆中的第0个数据依旧是最小的数据。
不断重复上述步骤,直至堆中只有一个数据时直接取出这个数据;

时间复杂度 O(nlogn)

代码实现

void heapSort(int *a,int len){
    for(int i=len-1;i>=1;i--){
        swap(a[i],a[0]);
        heapSortDown(a, 0, i);     
    }
}

归并排序 Merge Sort

(归并算法的种类其实有很多,这里只说一种相对简单的做法)

原理:基于分治思想,并模拟指针操作

简单的说就是,对于两个有序子序列,array[r..mid], array[mid+1..l], r为左指针, l为右指针;
先将它们合并到一个暂存序列 tempArray[] 中;
合并完成后将 tempArray[] 复制到 array[r..l] 中,不断重复这一过程;

时间复杂度:O(nlogn)

代码实现

void mergeSort(int r,int l){
    if(r == l) return;
    int mid = (r+l)/2;

    mergeSort(r,mid);
    mergeSort(mid+1,l);

    //合并
    int tempArr[SIZE];
    int r_1=r,r_2=mid+1;
    for(int i=r;i<=l;i++){
        if(r_1>mid)
            tempArr[i]=arr[r_2++];     
        else if(r_2>l)
            tempArr[i]=arr[r_1++];     
        else if(arr[r_1]>arr[r_2])    
            tempArr[i]=arr[r_2++];    
        else 
            tempArr[i]=arr[r_1++];     
    }

    //复制
    for(int i=r;i<=l;i++)
        arr[i]=tempArr[i];
}

希尔排序 Shell Sort

原理

1.将数组分为若干个相隔特定的增量的子序列,对于每个子序列进行插入排序
2.选择更小的增量,再将数组分割为多个子序列进行排序,不断重复这一过程,直到数组变成有序数列;

时间复杂度与其增量序列有关

代码实现

void ShellSort(int *a,int len){                            
    int d = len/2;                 //设初始增量为数组长度的一半             
    while(d>=1){
        InsertionSort(a, d, len);                           
        d = d/2;
    }
}

当时写这篇文章的时候,还是个大一的小孩,整理排序算法只是想分享给朋友们看看

过个两年再看这篇文章,修改了很多表述有问题的地方,以及已经忘了归并应该怎么写了 orz