合並排序經典演算法

1. 求歸並排序演算法！

歸並排序。

1.這里，在把數組暫時復制到臨時數組時，將第二個子數組中的順序顛倒了一下。這樣，兩個子數組從兩端開始處理，使得他們互相成為另一個數組的「檢查哨」。 這個方法是由R.Sedgewick發明的歸並排序的優化。

2.在數組小於某一閥值時，不繼續歸並，而直接使用插入排序，提高效率。這里根據Record的結構，將閥值定位 16。

#define THRESHOLD 16

typedef struct _Record{
int data; //數據
int key; //鍵值
}Record;

//供用戶調用的排序 函數
void Sort(Record Array[], Record TempArray, int left, int right){
TwoWayMergeSort(Array, TempArray, left, right);
}

//歸並排序
void TwoWayMergeSort(Record Array[], Record TempArray[],
int left, int right)
{
if(right <= left) return; //如果只含一個元素，直接返回
if( right-left+1 ){ //如果序列長度大於閥值，繼續遞歸
int middle = (left + right)/2;
Sort(Array, TempArray, left, middle); //對左面進行遞歸
Sort(Array, TempArray, left, right, middle); //對右面進行遞歸
Merge(Array, TempArray, left, right, middle); //合並
}
else{
//如果序列長度小於閥值，採用直接插入排序，達到最佳效果
ImproveInsertSorter(&Array[left], right-left+1);
}
}

//歸並過程
void Merge(Record Array[], Record TempArray[],
int left, int right, int middle)
{
int index1, index2; //兩個子序列的起始位置
int k;

復制左邊的子序列
for(int i=1; i<=middle; i++){
TempArray[i] = Array[i];
}

//復制右邊的子序列，但順序顛倒過來
for(int j=1; j<=right-middle; j++){
TempArray[right-j+1] = Array[j+middle];
}

//開始歸並
for(index1=left, index2=right, k=left; k<=right; k++){
if(TempArray[index1].key<TempArray[index2].key){
Array[k] = TempArray[index++];
}
else{
Array[k] = TempArray[index2--];
}
}
}

//當長度小於閥值時 使用的直接插入排序的代碼
void ImproveInsertSorter(Record Array[], int size){
Record TempRecord; //臨時變數

for(int i=1; i<size; i++){
TempRecord = Array[i];
int j = i-1;
//從i開始往前尋找記錄i的正確位置
while(j>=0 && TempRecord.key<Array[j].key){
Array[j+1] = Array[j];
j = j-1;
}

Array[j+1] = TempRecord;
}
}

終於敲完了。。。 第一次回答問題， 只是覺得好玩`

2. 數據結構--歸並排序與基數排序

一、歸並排序
歸並排序（MERGE-SORT）是利用歸並的思想實現的排序方法，該演算法採用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。將兩個或以上的有序表組合成一個新的有序表。
1、2-路歸並排序
初始序列含有n個記錄，可看成n個有序的子序列，每個子序列的長度為1，然後兩兩歸並，得到[n/2]個長度為2或1的有序子序列，再兩兩歸並，如此重復，直至得到一個長度為n的有序序列為止。
2、舉例

上圖中的最後一次合並，要將[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列，合並為最終序列[1,2,3,4,5,6,7,8]，實現步驟：

Tips：
排序演算法的穩定性：保證排序前2個相等的數，在序列中的前後位置順序和排序後它們兩個的前後位置順序相同。例如，Ai = Aj，Ai排序前位於Aj的前面，排序後Ai還位於Aj的前面。
穩定性的好處：排序演算法如果是穩定的，那麼從一個鍵上排序，然後再從另一個鍵上排序，第一個鍵排序的結果可以為第二個鍵排序所用。基數排序就 是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時是不會改變的。
排序演算法是否為穩定的是由具體演算法決定的，不穩定的演算法在某種條件下可以變為穩定的演算法，而穩定的演算法在某種條件下也可以變為不穩定的演算法。
例如，對於如下冒泡排序演算法，原本是穩定的排序演算法，如果將記錄交換的條件改成r[j]>=r[j+1]，則兩個相等的記錄就會交換位置，從而變成不穩定的演算法。

堆排序、快速排序、希爾排序、直接選擇排序不是穩定的排序演算法，而基數排序、冒泡排序、直接插入排序、折半插入排序、歸並排序是穩定的排序演算法。

一、基數排序
基數排序是一種藉助多關鍵字排序的思想對單邏輯關鍵字進行排序的方法。
1、什麼是多關鍵字
已知撲克牌中52張牌面的次序關系為：

1、最高位優先於最低位優先

假設有n個記錄的序列{R ₁ ，R ₂ ，...R _n }，且每個記錄R _i 中含有d個關鍵字(K _i ¹ ，K _i ² ，...，K _i ^d )，序列{R ₁ ，R ₂ ，...R _n }對關鍵字(K ¹ ，K ² ，...，K ^d )有序是指：對於序列中任意兩個記錄R _i 和R _j (1 <= i < j <= n)都滿足下列有序關系：(K _i ¹ ，K _i ² ，...，K _i ^d )<(K _j ¹ ，K _j ² ，...，K _j ^d )，其中K ¹ 稱為最高位關鍵字，K ^d 稱為最低位關鍵字。

實現多關鍵字排序的方法：
A、先對最高位關鍵字K ¹ 進行排序，間序列分成若乾子序列，每個子序列中的記錄都具有相同的K ¹ 值，然後分別對每個子序列對關鍵字K ² 進行排序，按K ² 值不同再分成若干更小的子序列，依次重復，直到對K ^d-1 進行排序後得到的每一子序列中的記錄都具有相同的關鍵字(K ¹ ，K ² ，...，K ^d-1 )，而後每個子序列分別對K ^d 進行排序，最後將所要子序列依次連接在一起成為一個有序序列，這種方法為「最高位優先(MSD)」
B、先從最低位關鍵字K ^d 進行排序，在對高一位的關鍵字K ^d-1 進行排序，依次重復，直至對K ¹ 進行排序後便成為一個有序序列。這種方法稱為「最低位優先(LSD)」。

三、內部排序方法的比較

結論：
1、表中的「簡單排序」指：除希爾排序外的所有插入排序，冒泡排序和簡單選擇排序，其中之間插入排序最簡單，當序列中的記錄「基本有序」或n值較小時，它是最佳的排序方法，因此常將他和其他排序方法（快排，歸並排序）結合在一起使用。
2、從平均時間性能看，快排最省時間，但他在最壞情況下的時間性能不如堆排序和歸並排序。在n較大，歸並排序所需時間比堆排序少，但所需的輔助存儲量最多。
3、基數排序適用於n值很大且關鍵字較小的序列。

3. 常見的排序演算法—選擇，冒泡，插入，快速，歸並

太久沒看代碼了，最近打算復習一下java，又突然想到了排序演算法，就把幾種常見的排序演算法用java敲了一遍，這里統一將無序的序列從小到大排列。

選擇排序是一種簡單直觀的排序演算法。它的工作原理是：第一次從待排序的數據元素中選出最小的一個元素，存放在序列的起始位置，然後再從剩餘的未排序元素中尋找到最小元素，繼續放在下一個位置，直到待排序元素個數為0。

選擇排序代碼如下：

public void Select_sort(int[] arr) {

int temp,index;

for( int i=0;i<10;i++) {

index = i;

for(int j = i + 1 ; j < 10 ; j++) {

if(arr[j] < arr[index])

index = j;

}

/*

temp = arr[i];

arr[i] = arr[index];

arr[index] = temp;

*/

swap(arr,i,index);

}

System.out.print("經過選擇排序後：");

for(int i = 0 ; i < 10 ; i++)

System.out.print( arr[i] +" ");

System.out.println("");

}

冒泡排序是一種比較基礎的排序演算法，其思想是相鄰的元素兩兩比較，較大的元素放後面，較小的元素放前面，這樣一次循環下來，最大元素就會歸位，若數組中元素個數為n，則經過（n-1）次後，所有元素就依次從小到大排好序了。整個過程如同氣泡冒起，因此被稱作冒泡排序。

選擇排序代碼如下：

public void Bubble_sort(int[] arr) {

int temp;

for(int i = 0 ; i < 9 ; i++) {

for(int j = 0 ; j < 10 - i - 1 ;j++) {

if(arr[j] > arr[j+1]) {

/*

temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

*/

swap(arr,j,j+1);

}

}

}

System.out.print("經過冒泡排序後：");

for(int i = 0 ; i < 10 ; i++)

System.out.print( arr[i] +" ");

System.out.println("");

}

插入排序也是一種常見的排序演算法，插入排序的思想是：創建一個與待排序數組等大的數組，每次取出一個待排序數組中的元素，然後將其插入到新數組中合適的位置，使新數組中的元素保持從小到大的順序。

插入排序代碼如下：

public void Insert_sort(int[] arr) {

int length = arr.length;

int[] arr_sort = new int[length];

int count = 0;

for(int i = 0;i < length; i++) {

if(count == 0) {

arr_sort[0] = arr[0];

}else if(arr[i] >= arr_sort[count - 1]) {

arr_sort[count] = arr[i];

}else if(arr[i] < arr_sort[0]) {

insert(arr,arr_sort,arr[i],0,count);

}else {

for(int j = 0;j < count - 1; j++) {

if(arr[i] >= arr_sort[j] && arr[i] < arr_sort[j+1]) {

insert(arr,arr_sort,arr[i],j+1,count);

break;

}

}

}

count++;

}

System.out.print("經過插入排序後：");

for(int i = 0 ; i < 10 ; i++)

System.out.print( arr_sort[i] +" ");

System.out.println("");

}

public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {

for(int i = count; i > index; i--)

arr_sort[i] = arr_sort[i-1];

arr_sort[index] = value;

}

快速排序的效率比冒泡排序演算法有大幅提升。因為使用冒泡排序時，一次外循環只能歸位一個值，有n個元素最多就要執行（n-1）次外循環。而使用快速排序時，一次可以將所有元素按大小分成兩堆，也就是平均情況下需要logn輪就可以完成排序。

快速排序的思想是：每趟排序時選出一個基準值（這里以首元素為基準值），然後將所有元素與該基準值比較，並按大小分成左右兩堆，然後遞歸執行該過程，直到所有元素都完成排序。

public void Quick_sort(int[] arr, int left, int right) {

if(left >= right)

return ;

int temp,t;

int j = right;

int i = left;

temp = arr[left];

while(i < j) {

while(arr[j] >= temp && i < j)

j--;

while(arr[i] <= temp && i < j)

i++;

if(i < j) {

t = arr[i];

arr[i] = arr[j];

arr[j] = t;

}

}

arr[left] = arr[i];

arr[i] = temp;

Quick_sort(arr,left, i - 1);

Quick_sort(arr, i + 1, right);

}

歸並排序是建立在歸並操作上的一種有效的排序演算法，歸並排序對序列的元素進行逐層折半分組，然後從最小分組開始比較排序，每兩個小分組合並成一個大的分組，逐層進行，最終所有的元素都是有序的。

public void Mergesort(int[] arr,int left,int right) {

if(right - left > 0) {

int[] arr_1 = new int[(right - left)/2 + 1];

int[] arr_2 = new int[(right - left + 1)/2];

int j = 0;

int k = 0;

for(int i = left;i <= right;i++) {

if(i <= (right + left)/2) {

arr_1[j++] = arr[i];

}else {

arr_2[k++] = arr[i];

}

}

Mergesort(arr_1,0,(right - left)/2);

Mergesort(arr_2,0,(right - left - 1)/2);

Merge(arr_1,arr_2,arr);

}

}

public void Merge(int[] arr_1,int[] arr_2,int[] arr) {

int i = 0;

int j = 0;

int k = 0;

int L1 = arr_1.length;

int L2 = arr_2.length;

while(i < L1 && j < L2) {

if(arr_1[i] <= arr_2[j]) {

arr[k] = arr_1[i];

i++;

}else {

arr[k] = arr_2[j];

j++;

}

k++;

}

if(i == L1) {

for(int t = j;j < L2;j++)

arr[k++] = arr_2[j];

}else {

for(int t = i;i < L1;i++)

arr[k++] = arr_1[i];

}

}

歸並排序這里我使用了left，right等變數，使其可以通用，並沒有直接用數字表示那麼明確，所以給出相關偽代碼，便於理解。

Mergesort(arr[0...n-1])

//輸入：一個可排序數組arr[0...n-1]

//輸出：非降序排列的數組arr[0...n-1]

if n>1

arr[0...n/2-1] to arr_1[0...(n+1)/2-1]//確保arr_1中元素個數>=arr_2中元素個數

//對於總個數為奇數時，arr_1比arr_2中元素多一個；對於總個數為偶數時，沒有影響

arr[n/2...n-1] to arr_2[0...n/2-1]

Mergesort(arr_1[0...(n+1)/2-1])

Mergesort(arr_2[0...n/2-1])

Merge(arr_1,arr_2,arr)

Merge(arr_1[0...p-1],arr_2[0...q-1],arr[0...p+q-1])

//輸入：兩個有序數組arr_1[0...p-1]和arr_2[0...q-1]

//輸出：將arr_1與arr_2兩數組合並到arr

int i<-0;j<-0;k<-0

while i

<p span="" do<="" j

if arr_1[i] <= arr_2[j]

arr[k] <- arr_1[i]

i<-i+1

else arr[k] <- arr_2[j];j<-j+1

k<-k+1

if i=p

arr_2[j...q-1] to arr[k...p+q-1]

else arr_1[i...p-1] to arr[k...p+q-1]

package test_1;

import java.util.Scanner;

public class Test01 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int[] arr_1 = new int[10];

for(int i = 0 ; i < 10 ; i++)

arr_1[i] = sc.nextInt();

Sort demo_1 = new Sort();

//1~5一次只能運行一個，若多個同時運行，則只有第一個有效，後面幾個是無效排序。因為第一個運行的已經將帶排序數組排好序。

demo_1.Select_sort(arr_1);//-----------------------1

//demo_1.Bubble_sort(arr_1);//---------------------2

/* //---------------------3

demo_1.Quick_sort(arr_1, 0 , arr_1.length - 1);

System.out.print("經過快速排序後：");

for(int i = 0 ; i < 10 ; i++)

System.out.print( arr_1[i] +" ");

System.out.println("");

*/

//demo_1.Insert_sort(arr_1);//--------------------4

/* //--------------------5

demo_1.Mergesort(arr_1,0,arr_1.length - 1);

System.out.print("經過歸並排序後：");

for(int i = 0 ; i < 10 ; i++)

System.out.print( arr_1[i] +" ");

System.out.println("");

*/

}

}

class Sort {

public void swap(int arr[],int a, int b) {

int t;

t = arr[a];

arr[a] = arr[b];

arr[b] = t;

}

public void Select_sort(int[] arr) {

int temp,index;

for( int i=0;i<10;i++) {

index = i;

for(int j = i + 1 ; j < 10 ; j++) {

if(arr[j] < arr[index])

index = j;

}

/*

temp = arr[i];

arr[i] = arr[index];

arr[index] = temp;

*/

swap(arr,i,index);

}

System.out.print("經過選擇排序後：");

for(int i = 0 ; i < 10 ; i++)

System.out.print( arr[i] +" ");

System.out.println("");

}

public void Bubble_sort(int[] arr) {

int temp;

for(int i = 0 ; i < 9 ; i++) {

for(int j = 0 ; j < 10 - i - 1 ;j++) {

if(arr[j] > arr[j+1]) {

/*

temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

*/

swap(arr,j,j+1);

}

}

}

System.out.print("經過冒泡排序後：");

for(int i = 0 ; i < 10 ; i++)

System.out.print( arr[i] +" ");

System.out.println("");

}

public void Quick_sort(int[] arr, int left, int right) {

if(left >= right)

return ;

int temp,t;

int j = right;

int i = left;

temp = arr[left];

while(i < j) {

while(arr[j] >= temp && i < j)

j--;

while(arr[i] <= temp && i < j)

i++;

if(i < j) {

t = arr[i];

arr[i] = arr[j];

arr[j] = t;

}

}

arr[left] = arr[i];

arr[i] = temp;

Quick_sort(arr,left, i - 1);

Quick_sort(arr, i + 1, right);

}

public void Insert_sort(int[] arr) {

int length = arr.length;

int[] arr_sort = new int[length];

int count = 0;

for(int i = 0;i < length; i++) {

if(count == 0) {

arr_sort[0] = arr[0];

}else if(arr[i] >= arr_sort[count - 1]) {

arr_sort[count] = arr[i];

}else if(arr[i] < arr_sort[0]) {

insert(arr,arr_sort,arr[i],0,count);

}else {

for(int j = 0;j < count - 1; j++) {

if(arr[i] >= arr_sort[j] && arr[i] < arr_sort[j+1]) {

insert(arr,arr_sort,arr[i],j+1,count);

break;

}

}

}

count++;

}

System.out.print("經過插入排序後：");

for(int i = 0 ; i < 10 ; i++)

System.out.print( arr_sort[i] +" ");

System.out.println("");

}

public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {

for(int i = count; i > index; i--)

arr_sort[i] = arr_sort[i-1];

arr_sort[index] = value;

}

public void Mergesort(int[] arr,int left,int right) {

if(right - left > 0) {

int[] arr_1 = new int[(right - left)/2 + 1];

int[] arr_2 = new int[(right - left + 1)/2];

int j = 0;

int k = 0;

for(int i = left;i <= right;i++) {

if(i <= (right + left)/2) {

arr_1[j++] = arr[i];

}else {

arr_2[k++] = arr[i];

}

}

Mergesort(arr_1,0,(right - left)/2);

Mergesort(arr_2,0,(right - left - 1)/2);

Merge(arr_1,arr_2,arr);

}

}

public void Merge(int[] arr_1,int[] arr_2,int[] arr) {

int i = 0;

int j = 0;

int k = 0;

int L1 = arr_1.length;

int L2 = arr_2.length;

while(i < L1 && j < L2) {

if(arr_1[i] <= arr_2[j]) {

arr[k] = arr_1[i];

i++;

}else {

arr[k] = arr_2[j];

j++;

}

k++;

}

if(i == L1) {

for(int t = j;j < L2;j++)

arr[k++] = arr_2[j];

}else {

for(int t = i;i < L1;i++)

arr[k++] = arr_1[i];

}

}

}

若有錯誤，麻煩指正，不勝感激。

4. [求助] 自然合並排序的演算法

#include "stdio.h" //輸入輸出的庫函數
#include "stdlib.h" //自然生成數據的庫函數
int n; //全局變數，數組的長度
//函數的定義
void zgb(int *p); //自然分組的規劃
void zgb1(int x,int y,int *q,int *p,int m); //遞歸實現的分治策略
void zgb2(int x,int y,int z,int *p); //排序函數
int main() //主函數
{
int i,m;
char ch=13; //變數的定義
while(1) //主菜單選擇的循環
{
if(ch==13); //判斷控制換行
system("cls"); //清屏
printf("------------請選擇：--------------\n1、運行程序。\n0、退出程序。\n"); //主菜單
scanf("%d",&m); //接受菜單選擇值
system("cls"); //清屏
if(!m) //判斷程序是否執行。
exit(0); //如果m的值非1，則執行退出
printf("請輸入數列的長度n。\n"); //提示語句
scanf("%d",&n); //從鍵盤輸入一個值給n，規定數組的長度
int *a=new int[n]; //定義原數據數組
printf("隨機數列如下：\n");
for(i=0; i<n; i++)
printf("%4d",a[i]=rand()%100); //動態生成數組的數據
printf("\n");
zgb(a); //調用自然分組的函數
printf("自然歸並排序的結果如下：\n");
for(i=0; i<n; i++)
printf("%4d",a[i]); //輸入最終排序號的結果數組
printf("\n");
scanf("%c%c",&ch,&ch); //接受最終的回車符，進入主菜單的下次循環
}
return 0;
}
void zgb(int *p) //自然分組函數
{
int i,m;
int *b=new int[n];//定義保存自然分組的起始下標值的數組
m=0;
b[0]=0;
for(i=1; i<n-1; i++)
if(p[i]>p[i+1]) //判斷取得起始下標的值
b[m+=1]=i+1;
printf("每次排序前的分段下標如下：\n");
while(1) //進入分治策略的循環
{
for(i=0; i<=m; i++)
printf("%d\t",b[i]); //輸出每次進入排序前的自然分組的起始下標值
printf("\n");
int k=0;
zgb1(0,m,b,p,m); //調用遞歸分治策略的函數
for(i=0; i<=m; i++)
{
if(b[i]!=-1&&b[k]==-1)
{
b[k]=b[i];
b[i]=-1; //合並後的起始下標的位子去除
}
if(b[k]!=-1)
k++;
}
m=k-1;
if(m<=0) //控制循環的退出
{
printf("0\n");
break;
}
}
}
void zgb1(int x,int y,int *q,int *p,int m) //分治策略函數
{
if(y-x==1) //判斷下標的值域
{
if(y==m) //判斷臨界值，選擇排序值的調用
zgb2(q[x],q[y],n,p);
else
zgb2(q[x],q[y],q[y+1],p); //調用排序函數
q[y]=-1;
}
int h=(x+y)/2; //計算規劃值
if(y-x>=2)
{
zgb1(x,h,q,p,m); //遞歸調用函數本身
zgb1(h+1,y,q,p,m);
}

}
/*
排序函數
*/
void zgb2(int x,int y,int z,int *p)
{
int i,j,k,s;
for(i=y; i<z; i++)
for(j=x; j<z; j++)
if(p[i]<p[j])
{
k=p[i];
p[i]=p[j];
p[j]=k;
}
}

5. 常見的幾種排序演算法總結

對於非科班生的我來說，演算法似乎對我來說是個難點，查閱了一些資料，趁此來了解一下幾種排序演算法。
首先了解一下，什麼是程序

關於排序演算法通常我們所說的往往指的是內部排序演算法，即數據記錄在內存中進行排序。
排序演算法大體可分為兩種：
一種是比較排序，時間復雜度O(nlogn) ~ O(n^2)，主要有：冒泡排序，選擇排序，插入排序，歸並排序，堆排序，快速排序等。
另一種是非比較排序，時間復雜度可以達到O(n)，主要有：計數排序，基數排序，桶排序等

冒泡排序它重復地走訪過要排序的元素，一次比較相鄰兩個元素，如果他們的順序錯誤就把他們調換過來，直到沒有元素再需要交換，排序完成。這個演算法的名字由來是因為越小(或越大)的元素會經由交換慢慢「浮」到數列的頂端。

選擇排序類似於冒泡排序，只不過選擇排序是首先在未排序的序列中找到最小值（最大值），放到序列的起始位置，然後再從剩餘未排序元素中繼續尋找最小（大）元素，放到已排序序列的末尾，以此類推，直到所有元素均排序完畢。

插入排序比冒泡排序和選擇排序更有效率，插入排序類似於生活中抓撲克牌來。
插入排序具體演算法描述，以數組[3, 2, 4, 5, 1]為例。

前面三種排序演算法只有教學價值，因為效率低，很少實際使用。歸並排序（Merge sort）則是一種被廣泛使用的排序方法。
它的基本思想是，將兩個已經排序的數組合並，要比從頭開始排序所有元素來得快。因此，可以將數組拆開，分成n個只有一個元素的數組，然後不斷地兩兩合並，直到全部排序完成。
以對數組[3, 2, 4, 5, 1] 進行從小到大排序為例，步驟如下：

有了merge函數，就可以對任意數組排序了。基本方法是將數組不斷地拆成兩半，直到每一半隻包含零個元素或一個元素為止，然後就用merge函數，將拆成兩半的數組不斷合並，直到合並成一整個排序完成的數組。

快速排序（quick sort）是公認最快的排序演算法之一，有著廣泛的應用。
快速排序演算法步驟

參考：
常用排序演算法總結(一)
阮一峰-演算法總結

6. 面試必會八大排序演算法（Python）

一、插入排序

介紹

插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據。

演算法適用於少量數據的排序，時間復雜度為O(n^2)。

插入排演算法是穩定的排序方法。

步驟

①從第一個元素開始，該元素可以認為已經被排序

②取出下一個元素，在已經排序的元素序列中從後向前掃描

③如果該元素（已排序）大於新元素，將該元素移到下一位置

④重復步驟3，直到找到已排序的元素小於或者等於新元素的位置

⑤將新元素插入到該位置中

⑥重復步驟2

排序演示

演算法實現

二、冒泡排序

介紹

冒泡排序（Bubble Sort）是一種簡單的排序演算法，時間復雜度為O(n^2)。

它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。

這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。

原理

循環遍歷列表，每次循環找出循環最大的元素排在後面；

需要使用嵌套循環實現：外層循環控制總循環次數，內層循環負責每輪的循環比較。

步驟

①比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

②對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。

③針對所有的元素重復以上的步驟，除了最後一個。

④持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

演算法實現：

三、快速排序

介紹

快速排序（Quicksort）是對冒泡排序的一種改進，借用了分治的思想，由C. A. R. Hoare在1962年提出。

基本思想

快速排序的基本思想是：挖坑填數 + 分治法。

首先選出一個軸值(pivot，也有叫基準的)，通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

實現步驟

①從數列中挑出一個元素，稱為 「基準」（pivot）；

②重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）；

③對所有兩個小數列重復第二步，直至各區間只有一個數。

排序演示

演算法實現

四、希爾排序

介紹

希爾排序（Shell Sort）是插入排序的一種，也是縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法，時間復雜度為：O(1.3n)。

希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

·插入排序在對幾乎已經排好序的數據操作時， 效率高， 即可以達到線性排序的效率；

·但插入排序一般來說是低效的， 因為插入排序每次只能將數據移動一位。

基本思想

①希爾排序是把記錄按下標的一定量分組，對每組使用直接插入演算法排序；

②隨著增量逐漸減少，每組包1含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法被終止。

排序演示

演算法實現

五、選擇排序

介紹

選擇排序(Selection sort)是一種簡單直觀的排序演算法，時間復雜度為Ο(n2)。

基本思想

選擇排序的基本思想：比較 + 交換。

第一趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；

第二趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；

以此類推，第 i 趟，在待排序記錄ri ~ r[n]中選出最小的記錄，將它與r[i]交換,使有序序列不斷增長直到全部排序完畢。

排序演示

選擇排序的示例動畫。紅色表示當前最小值，黃色表示已排序序列，藍色表示當前位置。

演算法實現

六、堆排序

介紹

堆排序（Heapsort）是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法，它是選擇排序的一種。

利用數組的特點快速指定索引的元素。

基本思想

堆分為大根堆和小根堆，是完全二叉樹。

大根堆的要求是每個節點的值不大於其父節點的值，即A[PARENT[i]] >=A[i]。

在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。

排序演示

演算法實現

七、歸並排序

介紹

歸並排序（Merge sort）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

基本思想

歸並排序演算法是將兩個（或兩個以上）有序表合並成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合並為整體有序序列。

演算法思想

自上而下遞歸法（假如序列共有n個元素）

① 將序列每相鄰兩個數字進行歸並操作，形成 floor(n/2)個序列，排序後每個序列包含兩個元素；

② 將上述序列再次歸並，形成 floor(n/4)個序列，每個序列包含四個元素；

③ 重復步驟②，直到所有元素排序完畢。

自下而上迭代法

① 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列；

② 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

③ 比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置；

④ 重復步驟③直到某一指針達到序列尾；

⑤ 將另一序列剩下的所有元素直接復制到合並序列尾。

排序演示

演算法實現

八、基數排序

介紹

基數排序（Radix Sort）屬於「分配式排序」，又稱為「桶子法」。

基數排序法是屬於穩定性的排序，其時間復雜度為O (nlog(r)m) ，其中 r 為採取的基數，而m為堆數。

在某些時候，基數排序法的效率高於其他的穩定性排序法。

基本思想

將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後，數列就變成一個有序序列。

基數排序按照優先從高位或低位來排序有兩種實現方案：

MSD（Most significant digital） 從最左側高位開始進行排序。先按k1排序分組, 同一組中記錄, 關鍵碼k1相等,再對各組按k2排序分成子組, 之後, 對後面的關鍵碼繼續這樣的排序分組, 直到按最次位關鍵碼kd對各子組排序後. 再將各組連接起來,便得到一個有序序列。MSD方式適用於位數多的序列。

LSD （Least significant digital）從最右側低位開始進行排序。先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序後便得到一個有序序列。LSD方式適用於位數少的序列。

排序效果

演算法實現

九、總結

各種排序的穩定性、時間復雜度、空間復雜度的總結：

平方階O(n²)排序：各類簡單排序：直接插入、直接選擇和冒泡排序；

從時間復雜度來說：

線性對數階O(nlog₂n)排序：快速排序、堆排序和歸並排序；

O(n1+§))排序，§是介於0和1之間的常數：希爾排序 ；

線性階O(n)排序：基數排序，此外還有桶、箱排序。

7. 常見演算法4、合並(歸並)排序 Merge sort

歸並排序，是創建在歸並操作上的一種有效的排序演算法。演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

假如如我這里有一組數據，歸並排序過程如下：

通俗點來說，就是先分割，再合並。分割的過程中其實可理解為就是以二分法將數組分割成最小單元，然後再按順序合並起來。

1、Python 3 ：

2、PHP：

8. 合並排序演算法

//你沒寫遞歸邊界

#include<stdio.h>
#include<stdlib.h>
voidmergesort(inta[],intn);
voidmerge(inta[],intb[],inti,intc[],intj);
intmain()
{
inta[20]={1,4,7,8,9,5,4,2,3,6,7,8,5,4,2,1,5,9,6,8},j;
mergesort(a,20);
for(j=0;j<20;j++)
{
printf("%d",a[j]);
}
return0;
}
voidmergesort(inta[],intn){
if(n<=1)
return;//遞歸邊界
inti,j;
int*b;
int*c;
b=(int*)malloc(sizeof(int)*(n/2));
c=(int*)malloc(sizeof(int)*(n-n/2));
for(i=0;i<n/2;i++){
b[i]=a[i];
}
for(j=0;j<n-n/2;j++){
c[j]=a[j+n/2];
}
mergesort(b,(n/2));
mergesort(c,(n-n/2));
merge(a,b,(n/2),c,(n-n/2));
}
voidmerge(inta[],intb[],intx,intc[],inty)
{
inti=0;
intj=0;
intk=0;
while((i<x)&&(j<y)){
if(b[i]<=c[j]){
a[k]=b[i];
i++;
}
else{
a[k]=c[j];
j++;
}
k++;
}
intl;
if(i==x){
for(l=j;l<y;l++){
a[k]=c[l];
k++;
}
}
else{
for(l=i;l<x;l++){
a[k]=b[l];
k++;
}
}
}

9. 歸並排序的演算法原理是什麼

歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用，歸並排序將兩個已排序的表合並成一個表。
歸並排序基本原理

通過對若干個有序結點序列的歸並來實現排序。
所謂歸並是指將若干個已排好序的部分合並成一個有序的部分。

歸並排序基本思想

設兩個有序的子序列(相當於輸入序列)放在同一序列中相鄰的位置上：array[low..m]，array[m + 1..high]，先將它們合並到一個局部的暫存序列 temp (相當於輸出序列)中，待合並完成後將 temp 復制回 array[low..high]中，從而完成排序。

在具體的合並過程中，設置 i，j 和 p 三個指針，其初值分別指向這三個記錄區的起始位置。合並時依次比較 array[i] 和 array[j] 的關鍵字，取關鍵字較小（或較大）的記錄復制到 temp[p] 中，然後將被復制記錄的指針 i 或 j 加 1，以及指向復制位置的指針 p加 1。重復這一過程直至兩個輸入的子序列有一個已全部復制完畢(不妨稱其為空)，此時將另一非空的子序列中剩餘記錄依次復制到 array 中即可。

10. Java 合並排序 求程序

網路文庫找了一個http://wenku..com/view/332fd62d453610661ed9f414.html
四、合並排序 1、基本思想
合並排序的基本操作是：首先將待排序序列劃分為兩個長度相等的子序列；然後分別對兩個子序列進行歸並排序，得到兩個有序的子序列；最後將兩個有序的子序列合並成一個有序數列。
MergeSort(A[2*n]) {
divide A[2*n] into A[1,……,n],A[n-1,……,2*n];//劃分 MergeSort(A[1,……,n]);//歸並排序前半個子序列
MergeSort(A[[n-1,……,2*n]);//歸並排序後半個子序列 Merge;//合並 }
2、演算法復雜度分析
合並步的時間復雜度為O(n)。合並排序演算法的時間復雜度為O(nlog2n)。
3、編程實現
public int[] MergeSort(int[] A, int[] tempA, int s, int t){
//如果序列中有一個以上的元素，即s<t則進行排序
if(s < t){
int center = (s + t) / 2;
MergeSort(A, tempA, s, center)
;//歸並排序前半個子序列
MergeSort(A, tempA, center + 1, t);
//歸並排序後半個子序列
Merge(A,tempA, s, center, t);
//合並
}
return tempA;
}

public int[] Merge(int[] A, int[] tempA, int s, int m, int t){ int n = t- s + 1;
//n為數據總個數
int i=s;j=m+1;k=s
while(i <= m&& j <= t){
//取A[i]和A[j]中較小者放入tempA[k]
if(A[i]<=A[j]){
tempA[k++] = A[i++]; }
else{
tempA[k++] = A[j++]; } }
if(i<=m) while(i<=m)
tempA[k++]=A[i++];//處理前一個子序列
else while(j<=t)
tempA[k++]=A[j++];//處理後一個子序列
return tempA;
}