常用的七大排序算法
1：冒泡排序：
// BubbleSort.cpp : 定義控制臺應用程序的入口點。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
冒泡排序是穩定排序
時間復雜度是 O(n^2)
*/
void Swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
void BubbleSort(int a[], int n)
{
int i, j;
for (i = 0; i < n; i++)
{
for (j = 1; j < n-i; j++)
{
if (a[j-1] > a[j])
{
Swap(a[j-1],a[j]);
}
}
}
}
void PrintNum(int a[],int n)
{
for (int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55};
int Num = sizeof(a)/sizeof(a[0]);
cout<<"排序前："<<endl;
PrintNum(a,Num);
BubbleSort(a,Num);
cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);
getchar();
return 0;
}
2：直接插入排序：
// InsertSort.cpp : 定義控制臺應用程序的入口點。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
插入排序是穩定排序
插入排序：O(n^2);
*/
void PrintNum(int a[],int n)
{
for (int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
}
void InsertSort(int a[], int n)
{
int i,j;
for ( i = 1; i < n; i++)//從1開始 a[0] 自動默認為有序
{
if (a[i] < a[i-1])
{
int temp = a[i];
for (j = i-1; j>=0 && a[j] > temp; j--)
{
a[j+1] = a[j];
}
a[j+1] = temp;//當遇到a[j] < temp的時候，a[j+1]賦值為temp
}
}
}
void InsertSort2(int a[], int n)
{
int i,j;
for(i = 1; i < n; i++)
{
if (a[i] < a[i-1])
{
int temp = a[i];
for (j= i -1;j>=0 && a[j] > temp;j--)
{
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55};
int Num = sizeof(a)/sizeof(a[0]);
cout<<"排序前："<<endl;
PrintNum(a,Num);
InsertSort2(a,Num);
cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);
getchar();
return 0;
}
3：希爾排序：
// ShellSort.cpp : 定義控制臺應用程序的入口點。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
希爾排序：
1：希爾排序的本質是分組直接插入排序；
2：把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，
當增量減至1時，整個文件恰被分成一組，算法便終止。
3：希爾排序不是穩定的排序
4：希爾排序的時間復雜度： 比O(n^2)稍微好一點
5：希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，
速度很快；當元素基本有序了，步長很小，插入排序對于有序的序列效率很高。所以，希爾排序的時間復雜度會比o(n^2)
好一些。
*/
void PrintNum(int a[],int n)
{
for (int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
}
void ShellSort(int a[], int n)
{
int i;
int gap;
for(gap = n/2; gap>0; gap /= 2)
{
for ( i = gap; i < n; i++)
{
if (a[i] < a[i-gap])
{
int temp = a[i];
int j;
for ( j = i-gap; j>=0 && a[j] > temp; j -= gap)
{
a[j+gap] = a[j];
}
a[j+gap] = temp;
}
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55};
int Num = sizeof(a)/sizeof(a[0]);
cout<<"排序前："<<endl;
PrintNum(a,Num);
ShellSort(a,Num);
cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);
getchar();
return 0;
} 4：選擇排序：
// SelectSort.cpp : 定義控制臺應用程序的入口點。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
直接選擇排序和直接插入排序類似，都將數據分為有序區和無序區，所不同的是直接插入排序
是將無序區的第一個元素直接插入到有序區以形成一個更大的有序區，而直接選擇排序是從無序區
選一個最小的元素直接放到了有序區的最后
數組 a[0...n-1]
1:初始時，數組全為無序區為 a[0...n-1].令i=0;
2:在無序區a[i...n-1]中選取一個最小的元素，將其與a[i]交換。交換之后a[0...i]就形成了一個有序區
3：i++并重復第二步知道 i == n-1.排序完成
選擇排序不是穩定排序
例如有： 5 8 5 2 9
第一次排序后 第一個 5與2 交換，那么兩個5的相對位置發生了變化。
時間復雜度也是O(n^2)不過比冒泡排序總體來說好一點
*/
void PrintNum(int a[],int n)
{
for (int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
}
void Swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
void SelectSort(int a[], int n)
{
int i,j,nMin;
for (int i = 0; i < n; i++)
{
nMin = i;
for (int j = i+1; j < n; j++)
{
if (a[j] < a[nMin])
{
nMin = j;
}
}
Swap(a[nMin],a[i]);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55};
int Num = sizeof(a)/sizeof(a[0]);
cout<<"排序前："<<endl;
PrintNum(a,Num);
SelectSort(a,Num);
cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);
getchar();
return 0;
}
5：歸并排序：
// MergeSort.cpp : 定義控制臺應用程序的入口點。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
歸并排序：
時間復雜度： O(NlogN)
是穩定的排序
歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。
將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個
有序表，稱為二路歸并。
歸并過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個有序表中的元素a[i]復制到r[k]中，并令i和k分別加上1；
否則將第二個有序表中的元素a[j]復制到r[k]中，并令j和k分別加上1，如此循環下去，直到其中一個有序表取完，然后再將
另一個有序表中剩余的元素復制到r中從下標k到下標t的單元。歸并排序的算法我們通常用遞歸實現，先把待排序區間[s,t]
以中點二分，接著把左邊子區間排序，再把右邊子區間排序，最后把左區間和右區間用一次歸并操作合并成有序的區間[s,t]。
*/
void PrintNum(int a[],int n)
{
for (int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
}
void mergeArray(int a[], int first, int mid, int last, int temp[])
{
int i = first;
int j = mid+1;
int m = mid;
int n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
{
temp[k++] = a[i++];
}
else
{
temp[k++] = a[j++];
}
}
while (i<=m)
{
temp[k++] = a[i++];
}
while (j<=n)
{
temp[k++] = a[j++];
}
for ( i = 0; i < k; i++)
{
a[first+i] = temp[i];
}
}
void mergeSort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first+last)/2;
mergeSort(a,first,mid,temp);//左邊排序
mergeSort(a,mid+1,last,temp);//右邊排序
mergeArray(a,first,mid,last,temp);//合并兩個有序數列
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n];
mergeSort(a,0,n-1,p);
delete[] p;
return true;
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55};
int Num = sizeof(a)/sizeof(a[0]);
cout<<"排序前："<<endl;
PrintNum(a,Num);
MergeSort(a,Num);
cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);
getchar();
return 0;
}
6：快速排序：
// QuickSort.cpp : 定義控制臺應用程序的入口點。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
快速排序的排序效率在同為O(NLogN)的幾種排序方法中效率較高
快速排序的思路： 挖坑填數+分治法
1：先從數組當中取一個數作為基準數 例如 a[0]
2: 分區過程，將比這個數大的數全部放到它的右邊，小于或等于它的數全部放到它的左邊
3：再對左右區間重復第二步，直到各區間只要一個數
快速排序不是穩定的排序，這也是它與歸并排序相比最大的缺點
eg： 3 2 4 5 6 2 7
第一步 從右往做找到比a[0]小的數字2，2填充到3 的位置，那么兩個2 的相對位置發生了變化，所以不是穩定的排序
*/
void PrintNum(int a[],int n)
{
for (int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
}
void QuickSort(int a[], int start, int end)
{
if (start > end)
{return;}
int i = start;
int j = end;
int k = a[i];//a[i]是第一個坑
while (i < j)
{
//從右往左找小于k的數來填 a[i]
while (i < j && a[j] >= k)
{
j--;
}
if (i < j)
{
a[i] = a[j];//將a[j]填到a[i]中，a[j]就是新的一個坑
}
//從左往右找大于k的數來填 a[j]
while (i < j && a[i] < k)
{
i++;
}
if (i < j)
{
a[j] = a[i];//將a[i]填到a[j]中，a[i]又是新的一個坑
}
}
//退出時，i=j，將k填到這個坑當中
a[i] = k;
QuickSort(a,i+1,end);
QuickSort(a,start,i-1);
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55};
int Num = sizeof(a)/sizeof(a[0]);
cout<<"排序前："<<endl;
PrintNum(a,Num);
QuickSort(a,0,Num-1);
cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);
getchar();
return 0;
}
7：堆排序：
// HeapSort.cpp : 定義控制臺應用程序的入口點。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
不穩定：就是大小相同的兩個數，經過排序后，最終位置與初始位置交換了。
快速排序：27 23 27 3以第一個27作為pivot中心點，則27與后面那個3交換，形成3 23 27 27，
排序經過一次結束，但最后那個27在排序之初先于初始位置3那個27，所以不穩定。
堆排序：比如：3 27 36 27，如果堆頂3先輸出，則，第三層的27（最后一個27）跑到堆頂，
然后堆穩定，繼續輸出堆頂，是剛才那個27，這樣說明后面的27先于第二個位置的27輸出，不穩定。
*/
void PrintNum(int a[],int n)
{
for (int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
}
void HeapAdjust(int a[], int start, int end)
{
int temp = a[start];
for (int i = 2*start + 1; i <= end ; i*=2)
{
if (i<end && a[i]<a[i+1])//左右孩子比較
{
++i;//如果左孩子的值小于右孩子的值，則++i, i為較大的記錄的下標
}
else
{
//i不做處理
}
if (temp > a[i]) //左右孩子中獲勝者與父親的比較
{
break;//如果左右孩子中最大的都比父節點的值小，則不需要做處理
}
else
{
//將孩子節點進行上位，則以孩子節點的位置進行下一輪的篩選
a[start] = a[i];
start = i;
}
}
a[start] = temp;
}
void HeapSort(int a[], int n)
{
//先建立大頂堆
for (int i = n/2; i >=0; --i)
{
HeapAdjust(a,i,n);
}
//進行排序
for (int i = n-1; i > 0 ; --i)
{
//最后一個元素和第一元素進行交換
int temp = a[i];
a[i] = a[0];
a[0] = temp;
//然后將剩下的無序元素繼續調整為大頂堆
HeapAdjust(a,0,i-1);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55};
int Num = sizeof(a)/sizeof(a[0]);
cout<<"排序前："<<endl;
PrintNum(a,Num);
HeapSort(a,Num);
cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);
getchar();
return 0;
}
本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！