直接插入排序

适用于少量数据的排序，直接插入排序是稳定的排序算法。
基本思想是：把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列。
平均时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定

#include <iostream>
using namespace std;
#define LENGTH 20

//直接插入排序：将第一个数据看做一个顺序表，将后面的数据一次插入表中
void InsertSort(int a[], int n)  
{  
for(int i= 1; i<n; i++){  
     int j= i-1;   //表中最后一个数据
    int x = a[i];        //复制为哨兵，即存储待排序元素  
    while(j>=0 && x < a[j]){  //查找在有序表的插入位置  (遍历表)
        a[j+1] = a[j];  
        j--;         //元素后移  
    }  
    a[j+1] = x;      //插入到正确位置  
}  
  
} 

int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}

cout<<"\n";
InsertSort(b,LENGTH);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

QQ_20190220165650

二分插入

基本思想是：直接插入排序是挨个的去比较，而二分插入排序则是利用二分搜索的原理，将待排序的元素与左侧已经排好序的队列的中间元素(n/2)进行比较
平均时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定

#include <iostream>
using namespace std;
#define LENGTH 20

//折半插入
void BInsertSort(int a[], int n)  
{  
for(int i= 1; i<n; i++){ 
    if(a[i] > a[i-1]){  //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
        continue;
    }
    int low=0,high=i;
    int x = a[i];        //复制为哨兵，即存储待排序元素  
    while(low<=high){  //查找在有序表的插入位置  (遍历表)
        int m=(low+high)/2;
        if(x<a[m]) {
            high=m-1;
        } else {
            low=m+1;
        }
    }  
    for(int j=i-1;j>=high+1;j--){
        a[j+1]=a[j];
    }
    a[high+1] = x;      //插入到正确位置  
}      
} 

int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}
cout<<"\n";
BInsertSort(b,LENGTH);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

QQ_20190220165650

希尔排序

基本思想是：希尔排序是在插入排序的基础上进行发展的，通过一个希尔增量先排序一定间隔的数据。待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
平均时间复杂度：O(N^3/2)
空间复杂度：O(1)
稳定性：不稳定

#include <iostream>
using namespace std;
#define LENGTH 20
void shellsort(int a[],int n) {  
for (int increment = n / 2; increment > 0; increment /= 2)
{
    for (int i = increment; i < n; i++)
    {
        int insert_num = a[i], j;
        for (j = i - increment; j >= 0; j -= increment)
        {
            if (a[j] > insert_num)
                a[j + increment] = a[j];
            else
                break;
        }
        a[j + increment] = insert_num;
    }
} 
}  
int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}
cout<<"\n";
shellsort(b,LENGTH);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

QQ_20190220165650

简单选择排序

基本思想是：要排序的一组数中，选出最小（最大）的一个数与第1个（最后）位置的数交换；然后在剩下的数当中再找最小（最大）的与第2个（倒数第二）位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止
平均时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定

#include <iostream>
using namespace std;
#define LENGTH 20
void SelectSort(int r[],int n) {  
int i ,j , min ,max, tmp;  
for (i=1 ;i <= n/2;i++) {    
    // 做不超过n/2趟选择排序   
    min = i; max = i ; //分别记录最大和最小关键字记录位置  
    for (j= i+1; j<= n-i; j++) {  
        if (r[j] > r[max]) {   
            max = j ; continue ;   
        }    
        if (r[j]< r[min]) {   
            min = j ;   
        }     
  }    
  //该交换操作还可分情况讨论以提高效率  
  tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;  
  tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;   

}   
}  
int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}

cout<<"\n";
SelectSort(b,LENGTH);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

QQ_20190220165650

冒泡排序

基本思想是：依次比较相邻的数据，将小数据放在前，大数据放在后
平均时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定

#include <iostream>
using namespace std;
#define LENGTH 20
//设置一个标记来标志一趟比较是否发生交换
//如果没有发生交换，则数组已经有序
void bubbleSort(int a[],int n)
{
bool flag;
for (int i = 0; i < n; i++)
{
    flag = false;
    for (int j = 0; j < n - 1 - i; j++)
    {
        if (a[j] > a[j+1])
        {
            swap(a[j], a[j+1]);
            flag = true;
        }
    }
    if (!flag)
        break;
}
}
int main()
{
int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}

cout<<"\n";
bubbleSort(b,LENGTH);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

QQ_20190220165650

快速排序

基本思想是：选择一个基准元素，把待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
时间复杂度：平均O(n*lgn);最坏O(n^2)
空间复杂度：最好O(lgn)，最坏O(n)，平均O(lgn)
稳定性：不稳定。

#include <iostream>
using namespace std;
#define LENGTH 20
void QuickSort(int a[], int low, int high)
{
if (low < high)
{
    int x = a[high];//将输入数组的最后一个数作为主元，用它来对数组进行划分
    int i = low - 1;//i是最后一个小于主元的数的下标
        for (int j = low; j < high; j++)//遍历下标由low到high-1的数
    {
        if (a[j] < x)//如果数小于主元的话就将i向前挪动一个位置，并且交换j和i所分别指向的数
        {
            int temp;
            i++;
             temp = a[i];
          a[i] = a[j];
          a[j] = temp;
         }
       }
       //经历上面的循环之后下标为从low到i（包括i）的数就均为小于x的数了，现在将主元和i+1位置上面的数进行交换
       a[high] = a[i + 1];
    a[i + 1] = x;

    int q = i + 1;
    QuickSort(a, low, q - 1);
    QuickSort(a, q + 1, high);
}
}

int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}

cout<<"\n";
QuickSort(b,0,LENGTH-1);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

QQ_20190220165650

堆排序

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
时间复杂度：O(nlogn)
空间复杂度：O(1)
稳定性：不稳定。

#include <iostream>
using namespace std;
#define LENGTH 20
// 递归方式构建大根堆(len是arr的长度，index是第一个非叶子节点的下标)
void adjust(int arr[], int len, int index)
{
int left = 2*index + 1; // index的左子节点
int right = 2*index + 2;// index的右子节点

int maxIdx = index;
if(left<len && arr[left] > arr[maxIdx])     maxIdx = left;
if(right<len && arr[right] > arr[maxIdx])     maxIdx = right;

if(maxIdx != index)
{
    swap(arr[maxIdx], arr[index]);
    adjust(arr, len, maxIdx);
}

}

// 堆排序
void heapSort(int arr[], int size)
{
// 构建大根堆（从最后一个非叶子节点向上）
for(int i=size/2 - 1; i >= 0; i--)
{
    adjust(arr, size, i);
}
 for(int i=0;i<size;i++){
     cout<<arr[i]<<" ";    
}
cout<<"\n";
// 调整大根堆
for(int i = size - 1; i >= 1; i--)
{
    swap(arr[0], arr[i]);           // 将当前最大的放置到数组末尾
    adjust(arr, i, 0);              // 将未完成排序的部分继续进行堆排序
}
}

int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
    
}

cout<<"\n";
heapSort(b,LENGTH);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

QQ_20190220165650

归并排序

基本思想是：将待排序序列递归分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列
时间复杂度：最差O(nlogn)
时间复杂度：平均O(nlogn)
空间复杂度：O(n)
稳定性：稳定

#include <iostream>
using namespace std;
#define LENGTH 20
/*该函数将数组下标范围[l,m]和[m+1,r]的有序序列合并成一个有序序列*/
void Merge(int *a,int l, int m, int r)
{
int begin1 = l;       
int begin2 = m + 1;  
int j=l; 
int k=0; 
int len = r-l+1;
int *b = new int[len];

while(begin1<=m && begin2<=r)  
{  
    if(a[begin1]<=a[begin2])  
        b[k++] = a[begin1++];  
    else  
        b[k++] = a[begin2++];  
}  
while(begin1<=m)  {
    b[k++] = a[begin1++];  
}
   
while(begin2<=r)  {
    b[k++] = a[begin2++]; 
}
    
   for(int i=0;i<len;i++)  
{  
    a[j++] = b[i];  
} 
delete []b;
}

 /*二路归并排序（递归实现）*/
void MergeSort(int *a, int l, int r)
{
if(l<r)
{
    int m = (l+r)/2;
    MergeSort(a,l,m);
    MergeSort(a,m+1,r);
    Merge(a,l,m,r);
}
}

int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}
cout<<"\n";
MergeSort(b,0,LENGTH-1);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

QQ_20190220165650

排序算法汇总-C++版

直接插入排序

二分插入

希尔排序

简单选择排序

冒泡排序

快速排序

堆排序

归并排序

热门文章

最新文章

相关课程

相关电子书

相关实验场景