六種排序演算法的演算法邏輯

Ⅰ 面試必會八大排序演算法（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)排序：基數排序，此外還有桶、箱排序。

Ⅱ 八大經典排序演算法原理及實現

該系列文章主要是記錄下自己暑假這段時間的學習筆記，暑期也在實習，抽空學了很多，每個方面的知識我都會另起一篇博客去記錄，每篇頭部主要是另起博客的鏈接。

冒泡排序演算法應該是大家第一個接觸的演算法，其原理都應該懂，但我還是想以自己的語言來敘述下其步奏：

按照計算時間復雜度的規則，去掉常數、去掉最高項系數，其復雜度為O(N^2)
冒泡排序及其復雜度分析

空間復雜度就是在交換元素時那個臨時變數所佔的內存

給定一個整數序列{6,1,2,3,4},每完成一次外層循環的結果為：

我們發現第一次外層循環之後就排序成功了，但是還是會繼續循環下去，造成了不必要的時間復雜度，怎麼優化？

冒泡排序都是相鄰元素的比較，當相鄰元素相等時並不會交換，因此冒泡排序演算法是穩定性演算法

插入排序是對冒泡排序的一種改進

插入排序的思想是數組是部分有序的，再將無序的部分插入有序的部分中去,如圖：
（圖片來自 這里 ）

空間復雜度就是在交換元素時那個臨時變數所佔的內存

插入排序的優化，有兩種方案：

文章後面會給出這兩種排序演算法

由於插入排序也是相鄰元素的比較，遇到相等的相鄰元素時不會發生交換，也不會造成相等元素之間的相對位置發生變化

其原理是從未排序的元素中選出最小值(最大值)放在已排序元素的後面

空間復雜度就是在交換元素時那個臨時變數所佔的內存

選擇排序是不穩定的，比如 3 6 3 2 4，第一次外層循環中就會交換第一個元素3和第四個元素2，那麼就會導致原序列的兩個3的相對位置發生變化

希爾排序算是改良版的插入排序演算法，所以也稱為希爾插入排序演算法

其原理是將序列分割成若乾子序列（由相隔某個 增量 的元素組成的），分別進行直接插入排序；接著依次縮小增量繼續進行排序，待整個序列基本有序時，再對全體元素進行插入排序，我們知道當序列基本有序時使用直接插入排序的效率很高。
上述描述只是其原理，真正的實現可以按下述步奏來：

希爾排序的效率取決於 增量值gap 的選取，這涉及到數學上尚未解決的難題，但是某些序列中復雜度可以為O(N 1.3)，當然最好肯定是O(N)，最壞是O(N 2)

空間復雜度就是在交換元素時那個臨時變數所佔的內存

希爾排序並不只是相鄰元素的比較，有許多跳躍式的比較，難免會出現相同元素之間的相對位置發生變化，所以希爾排序是不穩定的

理解堆排序，就必須得先知道什麼是堆？

二叉樹的特點：

當父節點的值總是大於子結點時為 最大堆 ；反之為 最小堆 ，下圖就為一個二叉堆

一般用數組來表示堆，下標為 i 的結點的父結點下標為(i-1)/2；其左右子結點分別為 (2 i + 1)、(2 i + 2)

怎麼將給定的數組序列按照堆的性質，調整為堆？

這里以建立最小堆為示例，

很明顯對於其葉子結點來說，已經是一個合法的子堆，所以做堆調整時，子節點沒有必要進行，這里只需從結點為A[4] = 50的結點開始做堆調整，即從（n/2 - 1）位置處向上開始做堆調整：

由於每次重新恢復堆的時間復雜度為O(logN)，共N - 1次重新恢復堆操作，再加上前面建立堆時N / 2次向下調整，每次調整時間復雜度也為O(logN)，二次操作時間相加還是O(N logN)。故堆排序的時間復雜度為O(N * logN)。

空間復雜度就是在交換元素時那個臨時變數所佔的內存

由於堆排序也是跨越式的交換數據，會導致相同元素之間的相對位置發生變化，則演算法不穩定。比如 5 5 5 ,堆化數組後將堆頂元素5與堆尾元素5交換，使得第一個5和第三個5的相對位置發生變化

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

快速排序在應該是大家經常看到、聽到的演算法，但是真正默寫出來是有難度的。希望大家看了下面 挖坑填數 方法後，能快速寫出、快速排序。

其原理就這么幾句話，但是現實起來並不是這么簡單，我們採取流行的一種方式 挖坑填數分治法

對於序列： 72 6 57 88 60 42 83 73 48 85

數組變為： 48 6 57 88 60 42 83 73 88 85
再重復上面的步驟，先從後向前找，再從前向後找：

數組變為： 48 6 57 42 60 72 83 73 88 85
可以看出a[5]前面的數字都小於它，a[5]後面的數字都大於它。因此再對a[0…4]和a[6…9]這二個子區間重復上述步驟就可以了

空間復雜度，主要是遞歸造成的棧空間的使用:

快速排序的優化主要在於基準數的選取

快速排序也是跨越式比較及交換數據，易導致相同元素之間的相對位置發生變化，所以快速排序不穩定

前面也說了二分查找排序是改進的插入排序，不同之處在於，在有序區間查找新元素插入位置時，為了減少比較次數提高效率，採用二分查找演算法進行插入位置的確定
具體步驟，設數組為a[0…n]：

二分查找插入位置，因為不是查找相等值，而是基於比較查插入合適的位置，所以必須查到最後一個元素才知道插入位置。
二分查找最壞時間復雜度：當2^X>=n時，查詢結束，所以查詢的次數就為x，而x等於log2n（以2為底，n的對數）。即O(log2n)
所以，二分查找排序比較次數為：x=log2n
二分查找插入排序耗時的操作有：比較 + 後移賦值。時間復雜度如下：

二分查找排序在交換數據時時進行移動，當遇到有相等值插入時也只會插入其後面，不會影響其相等元素之間的相對位置，所以是穩定的

白話經典演算法排序
冒泡排序選擇排序
快速排序復雜度分析
優化的插入排序

Ⅲ 我對幾種常見排序演算法的理解

排序演算法一般分為以下幾種： （1）非線性時間比較類排序：交換類排序（快速排序和冒泡排序）、插入類排序（簡單插入排序和希爾排序）、選擇類排序（簡單選擇排序和堆排序）、歸並排序（二路歸並排序和多路歸並排序）；（2）線性時間非比較類排序：計數排序、基數排序和桶排序。

Ⅳ 誰教我：數據結構的各種排序

1.快速排序

#include"stdio.h"
#define N 100
int a[N]={0};//存放要排序的數

int Qsort(int m,int n)//對數組中m到n的元素進行快速排序
{
int p,q;
int head,sign;
if(m!=n)//選定的數列不止一個元素
{
head=a[n];//選擇數列的末尾元素作為比較元素
p=m;//p標記數列的首元素
q=n-1;//標記末尾元素的前一個元素
sign=n;//記錄比較元素的位置，以其作為空位置
while(p<=q)//分別比較p、q所標記的元素與比較元素的大小，比其小的放在左邊，比其大的放在右邊
{
while(a[p]<head)//p所指元素比比較元素小，p右移
{
p++;
if(p>q)
{
break;
}
}
a[sign]=a[p];//將p所指元素移入空位置
sign=p;//記錄空餘位置
p++;
if(p>q)
{
break;
}
while(a[q]>head)//q所指元素比比較元素大，q左移
{
q--;
if(p>q)
{
break;
}
}
a[sign]=a[q];
sign=q;
q--;
}
a[sign]=head;//比較完成後，將比較元素移入空位置
if(sign-1>m)
{
Qsort(m,sign-1);//對m到sign-1的數列進行排序
}
if(sign+1<n)
{
Qsort(sign+1,n);//對sign+1到n的數列進行排序
}
}
return(1);
}

int Print(int m,int n)//對m到n的數組序列輸出
{
int i;
for(i=m;i<=n;i++)
{
printf("%d\n",a[i]);
}
return(1);
}

int main()
{
int n,i;
scanf("%d",&n);//輸入將要排序的數的個數
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);//輸入要排序的數
}
Qsort(0,n-1);
Print(0,n-1);
}
二、 詳細設計：重要函數中的演算法設計，實現流程，傳遞參數的說明；

三、調試分析與心得體會：
快速排序的思想時從數組序列中選定一個元素，將序列中其餘元素與其進行比較，將比其小的放在左邊，比其大的放在右邊，然後以比較元素為中點，將序列分成兩部分，再將它們分別進行快速排序，依次類推，直到序列中只有一個元素為止。

2.合並排序

#include"stdio.h"
#define N 10000
int a[N];//用a數組記錄所給無序數列
int b[N]={0};//用b數組記錄每次排序之後的a數組
int sign=0;
void Merge(int m,int mid,int n)//將兩個有序數列合並成為一個有序數列
{
int i,j,k;
i=k=m;
j=mid+1;
while(i<=mid&&j<=n)//依次比較兩個有序數列中的元素，從大到小將其放入b數組相應位置中
{
if(a[i]<a[j])
{
b[k]=a[i];
k++;
i++;
}
else
{
b[k]=a[j];
k++;
j++;
}
}
if(i<=mid)//將比較之後的剩餘元素放入b數組相應位置
{
while(i<=mid)
{
b[k]=a[i];
k++;
i++;
}
}
else
{
while(j<=n)
{
b[k]=a[j];
k++;
j++;
}
}
for(i=m;i<=n;i++)//將合並後的數列重新放入a數組相應位置
{
a[i]=b[i];
}
}
int Msort(int m,int n)//對所給無序數列進行排序
{
int mid;
if(n!=m)
{
mid=(n+m)/2; //將數列一分為二直到其只有一個元素
Msort(m,mid);
Msort(mid+1,n);
Merge(m,mid,n);//將分割後的數列重新合並起來
}
return(1);
}
void Print(int num)//將序列依次輸出
{
int i;
for(i=0;i<num;i++)
{
printf("%d\n",a[i]);
}
}
int main()
{
int sign;
int i;
int num;
scanf("%d",&num);//輸入將要排序的數的個數
for(i=0;i<num;i++)
{
scanf("%d",&a[i]);//依次輸入要排序的數
}
sign=Msort(0,num-1);
Print(num);//輸出完成排序後的有序數列
}
二、 詳細設計：重要函數中的演算法設計，實現流程，傳遞參數的說明；
三、調試分析與心得體會：
合並排序是排序的一種常用方法，其主要思想為：將一個無序數列依次分割直到其每個序列只有一個元素為止，然後再將兩個序列合並為一個有序數列，依此類推。

3.我的數據結構實驗課題（關於排序）

//問題描述：排序器
//要 求：實現以下六種排序演算法，將給定的不同規模大小的數據文件（data01.txt，data02.txt，data03.txt，data04.txt）進行排序，
//並將排序結果分別存儲到sorted01.txt，sorted02.txt，sorted03.txt和sorted04.txt文件中。
//1）、Shell排序； 2）、Quick排序
//3）、錦標賽排序； 4）、堆排序
//5）、歸並排序； 6）、基數排序
//在實現排序演算法1）~4）時，統計數據元素比較的次數和交換的次數，進而對這四種演算法在特定數據條件下的效率進行分析和評判。

#include"stdio.h"
#include"math.h"
#include"stdlib.h"
#include"malloc.h"
#define Maxsize 10000000
#define N 20
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define LEN sizeof(SqList)
#define Maxr 10
#define MAXNUM 100000000

typedef struct node{
int key;
int num;
};
typedef struct {
struct node r[Maxsize+1];
long length;
}SqList,*qSqList;
typedef struct node2{
struct node r;
struct node2 *next;
}RecType;
long shifttimes;//統計移動次數
long comparetimes;//統計比較次數

qSqList creat(char filename[])//讀入文件並且將數據保存
{
FILE *fp;
long i;
qSqList L;
L=(qSqList)malloc(LEN);
L->length=0;
if((fp=fopen(filename,"r"))==NULL)//文件不存在時終止程序
{
printf("cannot open file\n");
exit(0);
}
for(i=1;i<Maxsize+1;i++)
{
fscanf(fp,"%ld (%d)",&(L->r[i].key),&(L->r[i].num));
if(L->r[i].key<0)
break;
L->length++;//記錄讀入的數據長度
}
fclose(fp);
return(L);
}

void Print2(qSqList L)//將序列輸出到指定的文件中
{
long i;
FILE *fp;
char filename[N];
printf("\n\t請輸入存儲文件名：");
scanf("%s",filename);//輸入將要儲存的文件名
fp=fopen(filename,"w");
for(i=1;i<=L->length;i++)//將鏈表中數據逐一寫入文件中
{
fprintf(fp,"%d (%d)\n",L->r[i].key,L->r[i].num);
}
fclose(fp);
}

void Print(qSqList L)//列印數據個數以及排序過程中的比較次數和移動次數
{
printf("\n\t數據個數:%ld",L->length);
printf("\n\t比較次數:%ld",comparetimes);
printf("\n\t移動次數:%ld",shifttimes);
}

struct node Min1(struct node a,struct node b)//比較兩接點關鍵字的大小
{
struct node temp;
if(a.key>b.key)
temp=b;
else
temp=a;
comparetimes++;
return(temp);
}

qSqList shellinsert(qSqList L,int dk)//對順序表以dk為增量作直接插入排序
{
int i,j;
for(i=dk+1;i<=L->length;i++)
{
if(LT(L->r[i].key,L->r[i-dk].key))//將L->r[i]插入到有序增量子表
{
L->r[0]=L->r[i];//將L->r[i]暫時存儲在L->r[0]
shifttimes++;
for(j=i-dk;j>0&<(L->r[0].key,L->r[j].key);j-=dk)//記錄後移，查找插入位置
{
L->r[j+dk]=L->r[j];
comparetimes++;
shifttimes++;
}
if(j>0)
comparetimes++;
L->r[j+dk]=L->r[0];//插入
shifttimes++;
}
comparetimes++;
}
// Print(L);
return(L);
}

qSqList shell(qSqList L)//希爾排序
{
int i,t=0;
int k;
for(t=0;LQ(pow(2,t),(L->length+1));t++);
t=t-1;
// printf("%d",t);
for(i=1;i<=t;++i)
{
k=(int)pow(2,t-i+1)-1;//計算排序增量
L=shellinsert(L,k);
}
Print(L);
Print2(L);
return(L);
}

long Quicksort(qSqList L,long low,long high)//交換順序表L中子表L->r[low..high]的記錄，使樞軸記錄到位，並返回其所在位置
{
int pivotkey;
pivotkey=L->r[low].key;//用序列的第一個記錄作樞軸記錄
while(low<high)//從表的兩端交替地向中間掃描
{
while(low<high&&L->r[high].key>=pivotkey)//將比樞軸記錄小的記錄交換到低端
{
comparetimes++;
high--;
}
comparetimes++;
L->r[0]=L->r[low];
shifttimes++;
L->r[low]=L->r[high];
shifttimes++;
L->r[high]=L->r[0];
shifttimes++;
while(low<high&&L->r[low].key<=pivotkey)//將比樞軸記錄大的記錄交換到高端
{
comparetimes++;
low++;
}
comparetimes++;
L->r[0]=L->r[low];
shifttimes++;
L->r[low]=L->r[high];
shifttimes++;
L->r[high]=L->r[0];
shifttimes++;
}
return(low);//返回樞軸所在位置
}

qSqList Quick2(qSqList L,long low,long high)//對順序表L中的子序列L.r[low..high]作快速排序
{
long pivot;
if(low<high)//序列長度大於1
{
pivot=Quicksort(L,low,high);//將序列一分為二
Quick2(L,low,pivot-1);//對低位子表遞歸排序
Quick2(L,pivot+1,high);//對高位子表遞歸排序
}
return(L);
}

qSqList Quick(qSqList L)//對順序表作快速排序
{
long low,high;
low=1;//將第一個數據所在位置定義為低位
high=L->length;//將最後一個數據所在位置定義為高位
L=Quick2(L,low,high);//對順序表作快速排序
Print(L);
Print2(L);
return(L);
}

void TourSort(SqList *L,long n)//錦標賽排序
{
qSqList Lp;
long i=0,t=1,k=1,w;
while(t<n)//t表示完全二叉樹的結點個數
{
t=(long)pow(2,i);
i++;
}
t=2*t;
Lp=(qSqList)malloc((sizeof(SqList)));
Lp->length=t-1;
for(i=t-1;i>=t/2;i--)
{
if(k>n)
Lp->r[i].key=MAXNUM;
else
{
Lp->r[i]=L->r[k];

}
shifttimes++;
k++;
}
i=t-1;
while(i!=1)
{
Lp->r[i/2]=Min1(Lp->r[i],Lp->r[i-1]);
i-=2;
comparetimes++;
shifttimes++;
}
for(i=1;i<=n;i++)
{
L->r[i]=Lp->r[1];
shifttimes++;
w=1;
while(w<t/2)
{
if(Lp->r[2*w].key==Lp->r[w].key)
w*=2;
else
w=2*w+1;
}
Lp->r[w].key=MAXNUM;//將其賦為最大值
shifttimes++;
if(w%2)
Lp->r[w/2]=Lp->r[w-1];
else
Lp->r[w/2]=Lp->r[w+1];
shifttimes++;
while(w!=1)
{
if(w%2)
Lp->r[w/2]=Min1(Lp->r[w],Lp->r[w-1]);
else
Lp->r[w/2]=Min1(Lp->r[w],Lp->r[w+1]);
comparetimes++;
shifttimes++;
w/=2;
}
}
Print(L);
Print2(L);
}

void Heapadjust(qSqList L,long s,long m)//調整L->[s]的關鍵字，使L->r[s..m]成為一個大頂堆
{
long j;
struct node rc;
rc=L->r[s];
for(j=2*s;j<=m;j*=2)//沿key較大的接點向下篩選
{
if(j<m&<(L->r[j].key,L->r[j+1].key))//j為key較大的記錄的下標
{
j++;
comparetimes++;
}
if(!LT(rc.key,L->r[j].key))
{
comparetimes++;
break;
}
L->r[s]=L->r[j];//rc插入位置s
shifttimes++;
s=j;
}
L->r[s]=rc;//插入
shifttimes++;
}

qSqList Heap(qSqList L)//堆排序
{
long i;
for(i=L->length/2;i>0;--i)//把L建成大頂堆
Heapadjust(L,i,L->length);
for(i=L->length;i>1;--i)//將堆頂記錄和當前未經排序子序列中最後一個記錄交換
{
L->r[0]=L->r[1];
L->r[1]=L->r[i];
L->r[i]=L->r[0];
shifttimes=shifttimes+3;
Heapadjust(L,1,i-1);//將L重新調整為大頂堆
}
Print(L);
Print2(L);
return(L);
}

void Merge(qSqList L,int low,int m,int high)//將兩個有序表R[low..m]he R[m+1..high]歸並為一個有序表R[low,high]
{
int i=low,j=m+1,k=0;//k是temp的下標，i,j分別為第1，2段的下標
struct node *temp;
temp=(struct node*)malloc((high-low+1)*sizeof(struct node));//用於臨時保存有序序列
while(i<=m&&j<=high)//在第1段和第2段均未掃描完時循環
{
if(LT(L->r[j].key,L->r[i].key))//將第1段中的記錄放入temp中
{
temp[k]=L->r[j];
j++;
k++;
}
else//將第2段中的記錄放入temp中
{
temp[k]=L->r[i];
k++;
i++;
}
}
while(i<=m)//將第1段餘下的部分復制到temp
{
temp[k]=L->r[i];
k++;
i++;
}
while(j<=high)//將第2段餘下的部分復制到temp
{
temp[k]=L->r[j];
k++;
j++;
}
for(k=0,i=low;i<=high;i++,k++)//將temp復制回L中
{
L->r[i]=temp[k];
}
}

void MSort(qSqList L,int low,int high)//二路歸並排序
{
int m;
if (low<high)
{
m=(low+high)/2;
MSort(L,low,m);
MSort(L,m+1,high);
Merge(L,low,m,high);
}
}

void Merging(qSqList L)//歸並排序
{
MSort(L,1,L->length);
Print2(L);
}

void Radixsort(qSqList L)//基數排序
{
int g,i,j,k,d=2;
struct node2 *p,*s,*t,*head[10],*tail[10];//定義各鏈隊的首尾指針
for(i=1;i<=L->length;i++) //建立鏈表
{
s = (struct node2*)malloc(sizeof(struct node2));
s->r.key = L->r[i].key;
s->r.num= L->r[i].num;
if(i==1)
{
t = s;
p = s;
g++;}
else
{
t->next = s;
t = s;
g++;
}
t->next = NULL;
}
d=1;
for(i=1;i<6;i++)
{
for(j=0;j<10;j++)
{head[j] = tail[j] = NULL;} //初始化各鏈隊首、尾指針
while(p!=NULL)//對於原鏈表中的每個結點循環
{
k = p->r.key/d;
k = k%10;
if(head[k]==NULL)//進行分配
{
head[k]=p;
tail[k]=p;
}
else
{
tail[k]->next=p;
tail[k]=p;
}
p = p->next;//取下一個待排序的元素
}
p=NULL;
for(j=0;j<10;j++)//對每一個鏈隊循環
{
if(head[j]!=NULL)//進行搜集
{
if(p == NULL)
{
p = head[j];
t = tail[j];
}
else
{
t->next=head[j];
t = tail[j];
}
}
}
t->next=NULL;//最後一個結點的next置為空
d=d*10;
}
i=1;
while(p!=NULL)
{
L->r[i] = p->r;
i++;
p=p->next;}
Print2(L);
}

char chmenu()//對排序方法進行選擇
{
char ch;
printf("\n\t請選擇排序方法:"
"\n\t*************"
"\n\t1.Shell排序"
"\n\t2.Quick排序"
"\n\t3.錦標賽排序"
"\n\t4.堆排序"
"\n\t5.歸並排序"
"\n\t6.基排序"
"\n\t7.結束"
"\n\t*************");
do{
printf("\n\tplease choose (1-7):");
getchar();
ch=getchar();
}while(!(ch>'0'&&ch<'8'));
return(ch);
}

void main()
{
int a=1;
FILE *fp;
char ch,filename[N];
qSqList L;
while(a)
{
printf("\n\t請輸入讀入文件名:");//輸入要讀入的文件名
scanf("%s",filename);
if((fp=fopen(filename,"r"))==NULL)
{
printf("cannot open the file\n");
exit(0);
}
L=creat(filename);
while(1)
{
if((ch=chmenu())=='7')
break;
switch(ch)
{
case'1':{shifttimes=comparetimes=0;shell(L);}break;
case'2':{shifttimes=comparetimes=0;Quick(L);}break;
case'3':{shifttimes=comparetimes=0;TourSort(L,L->length);}break;
case'4':{shifttimes=comparetimes=0;Heap(L);}break;
case'5':{shifttimes=comparetimes=0;Merging(L);}break;
case'6':{shifttimes=comparetimes=0;Radixsort(L);}break;
}
}
printf("\n\t***************"
"\n\t1.繼續讀入文件"
"\n\t0.結束"
"\n\t***************");
do{
printf("\n\tplease choose (0-1):");
getchar();
scanf("%d",&a);
}while(!(a==1||a==0));

}
}

Ⅳ 排序演算法有哪些

1.插入排序—直接插入排序(Straight
Insertion
Sort)
2.
插入排序—希爾排序（Shell`s
Sort）
3.
選擇排序—簡單選擇排序（Simple
Selection
Sort）
4.
選擇排序—堆排序（Heap
Sort）
5.
交換排序—冒泡排序（Bubble
Sort）
6.
交換排序—快速排序（Quick
Sort）
7.
歸並排序（Merge
Sort）
8.
桶排序/基數排序(Radix
Sort)

Ⅵ 排序演算法有多少種

排序(Sorting) 是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。
排序就是把集合中的元素按照一定的次序排序在一起。一般來說有升序排列和降序排列2種排序，在演算法中有8中基本排序：
(1)冒泡排序；
(2)選擇排序；
(3)插入排序；
(4)希爾排序；
(5)歸並排序；
(6)快速排序；
(7)基數排序；
(8)堆排序；
(9)計數排序；
(10)桶排序。
插入排序
插入排序演算法是基於某序列已經有序排列的情況下，通過一次插入一個元素的方式按照原有排序方式增加元素。這種比較是從該有序序列的最末端開始執行，即要插入序列中的元素最先和有序序列中最大的元素比較，若其大於該最大元素，則可直接插入最大元素的後面即可，否則再向前一位比較查找直至找到應該插入的位置為止。插入排序的基本思想是，每次將1個待排序的記錄按其關鍵字大小插入到前面已經排好序的子序列中，尋找最適當的位置，直至全部記錄插入完畢。執行過程中，若遇到和插入元素相等的位置，則將要插人的元素放在該相等元素的後面，因此插入該元素後並未改變原序列的前後順序。我們認為插入排序也是一種穩定的排序方法。插入排序分直接插入排序、折半插入排序和希爾排序3類。
冒泡排序
冒泡排序演算法是把較小的元素往前調或者把較大的元素往後調。這種方法主要是通過對相鄰兩個元素進行大小的比較，根據比較結果和演算法規則對該二元素的位置進行交換，這樣逐個依次進行比較和交換，就能達到排序目的。冒泡排序的基本思想是，首先將第1個和第2個記錄的關鍵字比較大小，如果是逆序的，就將這兩個記錄進行交換，再對第2個和第3個記錄的關鍵字進行比較，依次類推，重復進行上述計算，直至完成第(n一1)個和第n個記錄的關鍵字之間的比較，此後，再按照上述過程進行第2次、第3次排序，直至整個序列有序為止。排序過程中要特別注意的是，當相鄰兩個元素大小一致時，這一步操作就不需要交換位置，因此也說明冒泡排序是一種嚴格的穩定排序演算法，它不改變序列中相同元素之間的相對位置關系。
選擇排序
選擇排序演算法的基本思路是為每一個位置選擇當前最小的元素。選擇排序的基本思想是，基於直接選擇排序和堆排序這兩種基本的簡單排序方法。首先從第1個位置開始對全部元素進行選擇，選出全部元素中最小的給該位置，再對第2個位置進行選擇，在剩餘元素中選擇最小的給該位置即可；以此類推，重復進行「最小元素」的選擇，直至完成第(n-1)個位置的元素選擇，則第n個位置就只剩唯一的最大元素，此時不需再進行選擇。使用這種排序時，要注意其中一個不同於冒泡法的細節。舉例說明：序列58539．我們知道第一遍選擇第1個元素「5」會和元素「3」交換，那麼原序列中的兩個相同元素「5」之間的前後相對順序就發生了改變。因此，我們說選擇排序不是穩定的排序演算法，它在計算過程中會破壞穩定性。
快速排序
快速排序的基本思想是:通過一趟排序演算法把所需要排序的序列的元素分割成兩大塊，其中，一部分的元素都要小於或等於另外一部分的序列元素，然後仍根據該種方法對劃分後的這兩塊序列的元素分別再次實行快速排序演算法，排序實現的整個過程可以是遞歸的來進行調用，最終能夠實現將所需排序的無序序列元素變為一個有序的序列。
歸並排序
歸並排序演算法就是把序列遞歸劃分成為一個個短序列，以其中只有1個元素的直接序列或者只有2個元素的序列作為短序列的遞歸出口，再將全部有序的短序列按照一定的規則進行排序為長序列。歸並排序融合了分治策略，即將含有n個記錄的初始序列中的每個記錄均視為長度為1的子序列，再將這n個子序列兩兩合並得到n/2個長度為2(當凡為奇數時會出現長度為l的情況)的有序子序列；將上述步驟重復操作，直至得到1個長度為n的有序長序列。需要注意的是，在進行元素比較和交換時，若兩個元素大小相等則不必刻意交換位置，因此該演算法不會破壞序列的穩定性，即歸並排序也是穩定的排序演算法。

Ⅶ Swift - 常用的排序演算法

排序演算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。

冒泡排序是一種簡單的排序演算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。

冒泡排序詳解

選擇排序(Selection-sort)是一種簡單直觀的排序演算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

n個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。具體演算法描述如下：

選擇排序詳解

插入排序（Insertion-Sort）是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

詳解插入排序

1959年Shell發明，第一個突破O(n2)的排序演算法，是簡單插入排序的改進版。它與插入排序的不同之處在於，它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。

希爾排序的提出，主要基於以下兩點：

先將整個待排序的記錄序列分割成為若乾子序列分別進行直接插入排序，具體演算法描述：

希爾排序詳情

歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為2-路歸並。

歸並排序詳解

快速排序的基本思想：通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體演算法描述如下：

快速排序詳解

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

堆排序詳解

計數排序不是基於比較的排序演算法，其核心在於將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。 作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

計數排序詳解

桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在於這個映射函數的確定。為了使桶排序更加高效，需要做到這兩點：

桶排序詳解

基數排序是一種非比較型整數排序演算法，其原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。由於整數也可以表達字元串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用於整數。

基數排序詳解

Ⅷ 幾種常見的排序演算法

for(i = 0; i < n; i++) for(j = 0; j < n - 1 - i; j++){if(arr[j] arr[j + 1]){arr[j] = arr[j] ^ arr[j+1]; arr[j+1] = arr[j] ^ arr[j+1]; arr[j] = arr[j] ^ arr[j+1];}}} 交換兩個數據，可以用用臨時變數，也可用以下的兩個方法a = a^b;b = a^b;a = a^b;或者 a = a + b;b = a - b;a = a - b;// 選擇排序 void SelectSort(int arr[], int n){int i, j;int min; for(i = 0; i < n - 1; i++){int index = 0; min = arr[i]; for(j = i + 1; j < n; j++) //找出 i+1 - n 無序區的最小者與arr[i]交換{if(arr[j] < min){min = arr[j];index = j;}}if(index != 0) //表明無序區有比arr[i]小的元素{arr[i] = arr[i]^arr[index]; arr[index] = arr[i]^arr[index]; arr[i] = arr[i]^arr[index];}}}感覺比冒泡法好多啦 //快速排序演算法

Ⅸ 排序演算法是怎樣的

一、背景介紹

在計算機科學與數學中，排序演算法（Sorting algorithm）是一種能將一串資料依照特定排序方式進行排列的一種演算法。

最常用到的排序方式是數字順序以及字典順序。

有效的排序演算法在一些演算法（例如搜尋演算法與合並演算法）中是重要的， 如此這些演算法才能得到正確解答。

排序演算法也用在處理文字資料以及產生人類可讀的輸出結果。

基本上，排序演算法的輸出必須遵守下列兩個原則：

1、輸出結果為遞增序列（遞增是針對所需的排序順序而言）；

2、輸出結果是原輸入的一種排列、或是重組；

雖然排序演算法是一個簡單的問題，但是從計算機科學發展以來，在此問題上已經有大量的研究。 更多的新演算法仍在不斷的被發明。

二、知識剖析

查找和排序演算法是演算法的入門知識，其經典思想可以用於很多演算法當中。因為其實現代碼較短，應用較常見。 所以在面試中經常會問到排序演算法及其相關的問題。但萬變不離其宗，只要熟悉了思想，靈活運用也不是難事。

一般在面試中最常考的是快速排序和冒泡排序，並且經常有面試官要求現場寫出這兩種排序的代碼。對這兩種排序的代碼一定要信手拈來才行。除此之外，還有插入排序、冒泡排序、堆排序、基數排序、桶排序等。

三、常見的幾種演算法：

冒泡演算法、選擇排序、插入排序、希爾排序、歸並排序、快速排序

演算法的特點：

1、有限性：一個演算法必須保證執行有限步之後結束。

2、確切性： 一個演算法的每一步驟必須有確切的定義。

3、輸入：一個演算法有零個或多個輸入，以刻畫運算對象的初始情況，所謂零個輸入是指演算法本身給定了初始條件。

4、輸出：一個演算法有一個或多個輸出。沒有輸出的演算法毫無意義。

5、可行性：演算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步，即每個計算步都可以在有限時間內完成（也稱之為有效性）。

Ⅹ 幾種排序演算法的比較

一、八大排序演算法的總體比較

4.3、堆的插入：

每次插入都是將新數據放在數組最後。可以發現從這個新數據的父結點到根結點必然為一個有序的數列，然後將這個新數據插入到這個有序數據中

（1）用大根堆排序的基本思想

先將初始數組建成一個大根堆，此對為初始的無序區；

再將最大的元素和無序區的最後一個記錄交換，由此得到新的無序區和有序區，且滿足<=的值；

由於交換後新的根可能違反堆性質，故將當前無序區調整為堆。然後再次將其中最大的元素和該區間的最後一個記錄交換，由此得到新的無序區和有序區，且仍滿足關系的值<=的值，同樣要將其調整為堆；

..........

直到無序區只有一個元素為止；

4.4：應用

尋找M個數中的前K個最小的數並保持有序；

時間復雜度：O(K)[創建K個元素最大堆的時間復雜度] +（M-K）*log(K)[對剩餘M-K個數據進行比較並每次對最大堆進行從新最大堆化]

5.希爾排序

（1）基本思想

先將整個待排序元素序列分割成若乾子序列（由相隔某個「增量」的元素組成的）分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序（因為直接插入排序在元素基本有序的情況下，效率很高）；

（2）適用場景

比較在希爾排序中是最主要的操作，而不是交換。用已知最好的步長序列的希爾排序比直接插入排序要快，甚至在小數組中比快速排序和堆排序還快，但在涉及大量數據時希爾排序還是不如快排；

6.歸並排序

（1）基本思想

首先將初始序列的n個記錄看成是n個有序的子序列，每個子序列的長度為1，然後兩兩歸並，得到n/2個長度為2的有序子序列，在此基礎上，再對長度為2的有序子序列進行兩兩歸並，得到若干個長度為4的有序子序列，以此類推，直到得到一個長度為n的有序序列為止；

（2）適用場景

若n較大，並且要求排序穩定，則可以選擇歸並排序；

7.簡單選擇排序

（1）基本思想

第一趟：從第一個記錄開始，將後面n-1個記錄進行比較，找到其中最小的記錄和第一個記錄進行交換；

第二趟：從第二個記錄開始，將後面n-2個記錄進行比較，找到其中最小的記錄和第2個記錄進行交換；

...........

第i趟：從第i個記錄開始，將後面n-i個記錄進行比較，找到其中最小的記錄和第i個記錄進行交換；

以此類推，經過n-1趟比較，將n-1個記錄排到位，剩下一個最大記錄直接排在最後；