常用的七大排序算法
來源：程序員人生 發(fā)布時(shí)間：2015-03-05 08:37:10 閱讀次數(shù)：2437次
1：冒泡排序：
// BubbleSort.cpp : 定義控制臺利用程序的入口點(diǎn)。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
冒泡排序是穩(wěn)定排序
時(shí)間復(fù)雜度是 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⑴] > a[j])
{
Swap(a[j⑴],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 : 定義控制臺利用程序的入口點(diǎn)。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
插入排序是穩(wěn)定排序
插入排序：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⑴])
{
int temp = a[i];
for (j = i⑴; j>=0 && a[j] > temp; j--)
{
a[j+1] = a[j];
}
a[j+1] = temp;//當(dāng)遇到a[j] < temp的時(shí)候，a[j+1]賦值為temp
}
}
}
void InsertSort2(int a[], int n)
{
int i,j;
for(i = 1; i < n; i++)
{
if (a[i] < a[i⑴])
{
int temp = a[i];
for (j= i ⑴;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 : 定義控制臺利用程序的入口點(diǎn)。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
希爾排序：
1：希爾排序的本質(zhì)是分組直接插入排序；
2：把記錄按下標(biāo)的1定增量分組，對每組使用直接插入排序算法排序；隨著增量逐步減少，每組包括的關(guān)鍵詞愈來愈多，
當(dāng)增量減至1時(shí)，全部文件恰被分成1組，算法便終止。
3：希爾排序不是穩(wěn)定的排序
4：希爾排序的時(shí)間復(fù)雜度： 比O(n^2)略微好1點(diǎn)
5：希爾排序是依照不同步長對元素進(jìn)行插入排序，當(dāng)剛開始元素很無序的時(shí)候，步長最大，所以插入排序的元素個數(shù)很少，
速度很快；當(dāng)元素基本有序了，步長很小，插入排序?qū)τ行虻男蛄行Я芨摺Ｋ裕柵判虻臅r(shí)間復(fù)雜度會比o(n^2)
好1些。
*/
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 : 定義控制臺利用程序的入口點(diǎn)。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
直接選擇排序和直接插入排序類似，都將數(shù)據(jù)分為有序區(qū)和無序區(qū)，所不同的是直接插入排序
是將無序區(qū)的第1個元素直接插入到有序區(qū)以構(gòu)成1個更大的有序區(qū)，而直接選擇排序是從無序區(qū)
選1個最小的元素直接放到了有序區(qū)的最后
數(shù)組 a[0...n⑴]
1:初始時(shí)，數(shù)組全為無序區(qū)為 a[0...n⑴].令i=0;
2:在無序區(qū)a[i...n⑴]當(dāng)選取1個最小的元素，將其與a[i]交換。交換以后a[0...i]就構(gòu)成了1個有序區(qū)
3：i++并重復(fù)第2步知道 i == n⑴.排序完成
選擇排序不是穩(wěn)定排序
例如有： 5 8 5 2 9
第1次排序后 第1個 5與2 交換，那末兩個5的相對位置產(chǎn)生了變化。
時(shí)間復(fù)雜度也是O(n^2)不過比冒泡排序整體來講好1點(diǎn)
*/
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 : 定義控制臺利用程序的入口點(diǎn)。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
歸并排序：
時(shí)間復(fù)雜度： O(NlogN)
是穩(wěn)定的排序
歸并排序是建立在歸并操作上的1種有效的排序算法,該算法是采取分治法（Divide and Conquer）的1個非常典型的利用。
將已有序的子序列合并，得到完全有序的序列；即先使每一個子序列有序，再使子序列段間有序。若將兩個有序表合并成1個
有序表，稱為2路歸并。
歸并進(jìn)程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第1個有序表中的元素a[i]復(fù)制到r[k]中，并令i和k分別加上1；
否則將第2個有序表中的元素a[j]復(fù)制到r[k]中，并令j和k分別加上1，如此循環(huán)下去，直到其中1個有序表取完，然后再將
另外一個有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)t的單元。歸并排序的算法我們通經(jīng)常使用遞歸實(shí)現(xiàn)，先把待排序區(qū)間[s,t]
以中點(diǎn)2分，接著把左側(cè)子區(qū)間排序，再把右側(cè)子區(qū)間排序，最后把左區(qū)間和右區(qū)間用1次歸并操作合并成有序的區(qū)間[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);//左側(cè)排序
mergeSort(a,mid+1,last,temp);//右側(cè)排序
mergeArray(a,first,mid,last,temp);//合并兩個有序數(shù)列
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n];
mergeSort(a,0,n⑴,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 : 定義控制臺利用程序的入口點(diǎn)。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
快速排序的排序效力在同為O(NLogN)的幾種排序方法中效力較高
快速排序的思路： 挖坑填數(shù)+分治法
1：先從數(shù)組當(dāng)中取1個數(shù)作為基準(zhǔn)數(shù) 例如 a[0]
2: 分區(qū)進(jìn)程，將比這個數(shù)大的數(shù)全部放到它的右側(cè)，小于或等于它的數(shù)全部放到它的左側(cè)
3：再對左右區(qū)間重復(fù)第2步，直到各區(qū)間只要1個數(shù)
快速排序不是穩(wěn)定的排序，這也是它與歸并排序相比最大的缺點(diǎn)
eg： 3 2 4 5 6 2 7
第1步 從右往做找到比a[0]小的數(shù)字2，2填充到3 的位置，那末兩個2 的相對位置產(chǎn)生了變化，所以不是穩(wěn)定的排序
*/
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]是第1個坑
while (i < j)
{
//從右往左找小于k的數(shù)來填 a[i]
while (i < j && a[j] >= k)
{
j--;
}
if (i < j)
{
a[i] = a[j];//將a[j]填到a[i]中，a[j]就是新的1個坑
}
//從左往右找大于k的數(shù)來填 a[j]
while (i < j && a[i] < k)
{
i++;
}
if (i < j)
{
a[j] = a[i];//將a[i]填到a[j]中，a[i]又是新的1個坑
}
}
//退出時(shí)，i=j，將k填到這個坑當(dāng)中
a[i] = k;
QuickSort(a,i+1,end);
QuickSort(a,start,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);
QuickSort(a,0,Num⑴);
cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);
getchar();
return 0;
}
7：堆排序：
// HeapSort.cpp : 定義控制臺利用程序的入口點(diǎn)。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
不穩(wěn)定：就是大小相同的兩個數(shù)，經(jīng)過排序后，終究位置與初始位置交換了。
快速排序：27 23 27 3以第1個27作為pivot中心點(diǎn)，則27與后面那個3交換，構(gòu)成3 23 27 27，
排序經(jīng)過1次結(jié)束，但最后那個27在排序之初先于初始位置3那個27，所以不穩(wěn)定。
堆排序：比如：3 27 36 27，如果堆頂3先輸出，則，第3層的27（最后1個27）跑到堆頂，
然后堆穩(wěn)定，繼續(xù)輸出堆頂，是剛才那個27，這樣說明后面的27先于第2個位置的27輸出，不穩(wěn)定。
*/
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為較大的記錄的下標(biāo)
}
else
{
//i不做處理
}
if (temp > a[i]) //左右孩子中獲勝者與父親的比較
{
break;//如果左右孩子中最大的都比父節(jié)點(diǎn)的值小，則不需要做處理
}
else
{
//將孩子節(jié)點(diǎn)進(jìn)行上位，則以孩子節(jié)點(diǎn)的位置進(jìn)行下1輪的挑選
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);
}
//進(jìn)行排序
for (int i = n⑴; i > 0 ; --i)
{
//最后1個元素和第1元素進(jìn)行交換
int temp = a[i];
a[i] = a[0];
a[0] = temp;
//然后將剩下的無序元素繼續(xù)調(diào)劑為大頂堆
HeapAdjust(a,0,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);
HeapSort(a,Num);
cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);
getchar();
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
