直接插入排序

适用于少量資料的排序，直接插入排序是穩定的排序算法。

基本思想是：把待排序的紀錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的紀錄插入完為止，得到一個新的有序序列。

平均時間複雜度：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;
}

二分插入

基本思想是：直接插入排序是挨個的去比較，而二分插入排序則是利用二分搜尋的原理，将待排序的元素與左側已經排好序的隊列的中間元素(n/2)進行比較

#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;
}

希爾排序

基本思想是：希爾排序是在插入排序的基礎上進行發展的，通過一個希爾增量先排序一定間隔的資料。待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

平均時間複雜度：O(N^3/2)

穩定性：不穩定

#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;
}

簡單選擇排序

基本思想是：要排序的一組數中，選出最小（最大）的一個數與第1個（最後）位置的數交換；然後在剩下的數當中再找最小（最大）的與第2個（倒數第二）位置的數交換，依次類推，直到第n-1個元素（倒數第二個數）和第n個元素（最後一個數）比較為止

#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;
}

冒泡排序

基本思想是：依次比較相鄰的資料，将小資料放在前，大資料放在後

空間複雜度：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;
}

快速排序

基本思想是：選擇一個基準元素，把待排序的記錄分割成獨立的兩部分，其中一部分記錄的元素值均比基準元素值小。另一部分記錄的元素值比基準值大。然後分别對這兩部分記錄用同樣的方法繼續進行排序，直到整個序列有序。

時間複雜度：平均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;
}

堆排序

堆是具有以下性質的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆。

基本思想是：将待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。将其與末尾元素進行交換，此時末尾就為最大值。然後将剩餘n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反複執行，便能得到一個有序序列了。

時間複雜度：O(nlogn)

#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;
}

歸并排序

基本思想是：将待排序序列遞歸分為若幹個子序列，每個子序列是有序的。然後再把有序子序列合并為整體有序序列

時間複雜度：最差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;
}

排序算法彙總-C++版直接插入排序二分插入希爾排序簡單選擇排序冒泡排序快速排序堆排序歸并排序

直接插入排序

二分插入

希爾排序

簡單選擇排序

冒泡排序

快速排序

堆排序

歸并排序

繼續閱讀

MapReduce的幾個企業級經典面試案例MapReduce的幾個企業級經典面試案例

[HTML5]自定義屬性 data-* 和 jQuery.data 詳解

9.spark Core 進階2--Cashe

2021-2025年中國運動療法（KT）帶行業市場供需與戰略研究報告

C++ 第十五周報告1--《冒泡法排序》

2021年危險化學品經營機關安全管理人員考試題庫及危險化學品經營機關安全管理人員考試技巧

淺談企業活動中進行資料分析的重要性

C++實作簡單順序表

無人機--飛控科普

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

Ambari介紹和架構原理

NOSQL安全攻擊

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

win10本地scala和spark安裝安裝scala安裝spark