計算機排序演算法

㈠ 排序演算法有多少種

排序(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的有序長序列。需要注意的是，在進行元素比較和交換時，若兩個元素大小相等則不必刻意交換位置，因此該演算法不會破壞序列的穩定性，即歸並排序也是穩定的排序演算法。

㈡ C語言排序

//總共給你整理了7種排序演算法：希爾排序，鏈式基數排序，歸並排序
//起泡排序，簡單選擇排序，樹形選擇排序，堆排序,先自己看看吧，
//看不懂可以再問身邊的人或者查資料,既然可以上網，我相信你所在的地方信息流通方式應該還行,所有的程序全部在VC++6.0下編譯通過
//希爾排序
#include<stdio.h>
typedef int InfoType; // 定義其它數據項的類型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項，具體類型在主程中定義
};

struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
void ShellInsert(SqList &L,int dk)
{ // 對順序表L作一趟希爾插入排序。本演算法是和一趟直接插入排序相比，
// 作了以下修改：
// 1.前後記錄位置的增量是dk,而不是1;
// 2.r[0]只是暫存單元,不是哨兵。當j<=0時,插入位置已找到。演算法10.4
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[0]
for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk)
L.r[j+dk]=L.r[j]; // 記錄後移，查找插入位置
L.r[j+dk]=L.r[0]; // 插入
}
}

void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
printf("\n");
}

void print1(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}

void ShellSort(SqList &L,int dlta[],int t)
{ // 按增量序列dlta[0..t-1]對順序表L作希爾排序。演算法10.5
int k;
for(k=0;k<t;++k)
{
ShellInsert(L,dlta[k]); // 一趟增量為dlta[k]的插入排序
printf("第%d趟排序結果: ",k+1);
print(L);
}
}

#define N 10
#define T 3
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8},{55,9},{4,10}};
SqList l;
int dt[T]={5,3,1}; // 增量序列數組
for(int i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前: ");
print(l);
ShellSort(l,dt,T);
printf("排序後: ");
print1(l);
}

/*****************************************************************/
//鏈式基數排序
typedef int InfoType; // 定義其它數據項的類型
typedef int KeyType; // 定義RedType類型的關鍵字為整型
struct RedType // 記錄類型(同c10-1.h)
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項
};
typedef char KeysType; // 定義關鍵字類型為字元型
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函數結果狀態代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函數的類型,其值是函數結果狀態代碼，如OK等
typedef int Boolean; // Boolean是布爾類型,其值是TRUE或FALSE
#define MAX_NUM_OF_KEY 8 // 關鍵字項數的最大值
#define RADIX 10 // 關鍵字基數，此時是十進制整數的基數
#define MAX_SPACE 1000
struct SLCell // 靜態鏈表的結點類型
{
KeysType keys[MAX_NUM_OF_KEY]; // 關鍵字
InfoType otheritems; // 其它數據項
int next;
};

struct SLList // 靜態鏈表類型
{
SLCell r[MAX_SPACE]; // 靜態鏈表的可利用空間，r[0]為頭結點
int keynum; // 記錄的當前關鍵字個數
int recnum; // 靜態鏈表的當前長度
};

typedef int ArrType[RADIX];
void InitList(SLList &L,RedType D[],int n)
{ // 初始化靜態鏈表L（把數組D中的數據存於L中）
char c[MAX_NUM_OF_KEY],c1[MAX_NUM_OF_KEY];
int i,j,max=D[0].key; // max為關鍵字的最大值
for(i=1;i<n;i++)
if(max<D[i].key)
max=D[i].key;
L.keynum=int(ceil(log10(max)));
L.recnum=n;
for(i=1;i<=n;i++)
{
L.r[i].otheritems=D[i-1].otherinfo;
itoa(D[i-1].key,c,10); // 將10進制整型轉化為字元型,存入c
for(j=strlen(c);j<L.keynum;j++) // 若c的長度<max的位數,在c前補'0'
{
strcpy(c1,"0");
strcat(c1,c);
strcpy(c,c1);
}
for(j=0;j<L.keynum;j++)
L.r[i].keys[j]=c[L.keynum-1-j];
}
}

int ord(char c)
{ // 返回k的映射(個位整數)
return c-'0';
}

void Distribute(SLCell r[],int i,ArrType f,ArrType e) // 演算法10.15
{ // 靜態鍵表L的r域中記錄已按(keys[0],…,keys[i-1])有序。本演算法按
// 第i個關鍵字keys[i]建立RADIX個子表,使同一子表中記錄的keys[i]相同。
// f[0..RADIX-1]和e[0..RADIX-1]分別指向各子表中第一個和最後一個記錄
int j,p;
for(j=0;j<RADIX;++j)
f[j]=0; // 各子表初始化為空表
for(p=r[0].next;p;p=r[p].next)
{
j=ord(r[p].keys[i]); // ord將記錄中第i個關鍵字映射到[0..RADIX-1]
if(!f[j])
f[j]=p;
else
r[e[j]].next=p;
e[j]=p; // 將p所指的結點插入第j個子表中
}
}

int succ(int i)
{ // 求後繼函數
return ++i;
}

void Collect(SLCell r[],ArrType f,ArrType e)
{ // 本演算法按keys[i]自小至大地將f[0..RADIX-1]所指各子表依次鏈接成
// 一個鏈表，e[0..RADIX-1]為各子表的尾指針。演算法10.16
int j,t;
for(j=0;!f[j];j=succ(j)); // 找第一個非空子表，succ為求後繼函數
r[0].next=f[j];
t=e[j]; // r[0].next指向第一個非空子表中第一個結點
while(j<RADIX-1)
{
for(j=succ(j);j<RADIX-1&&!f[j];j=succ(j)); // 找下一個非空子表
if(f[j])
{ // 鏈接兩個非空子表
r[t].next=f[j];
t=e[j];
}
}
r[t].next=0; // t指向最後一個非空子表中的最後一個結點
}

void printl(SLList L)
{ // 按鏈表輸出靜態鏈表
int i=L.r[0].next,j;
while(i)
{
for(j=L.keynum-1;j>=0;j--)
printf("%c",L.r[i].keys[j]);
printf(" ");
i=L.r[i].next;
}
}

void RadixSort(SLList &L)
{ // L是採用靜態鏈表表示的順序表。對L作基數排序，使得L成為按關鍵字
// 自小到大的有序靜態鏈表，L.r[0]為頭結點。演算法10.17
int i;
ArrType f,e;
for(i=0;i<L.recnum;++i)
L.r[i].next=i+1;
L.r[L.recnum].next=0; // 將L改造為靜態鏈表
for(i=0;i<L.keynum;++i)
{ // 按最低位優先依次對各關鍵字進行分配和收集
Distribute(L.r,i,f,e); // 第i趟分配
Collect(L.r,f,e); // 第i趟收集
printf("第%d趟收集後:\n",i+1);
printl(L);
printf("\n");
}
}

void print(SLList L)
{ // 按數組序號輸出靜態鏈表
int i,j;
printf("keynum=%d recnum=%d\n",L.keynum,L.recnum);
for(i=1;i<=L.recnum;i++)
{
printf("keys=");
for(j=L.keynum-1;j>=0;j--)
printf("%c",L.r[i].keys[j]);
printf(" otheritems=%d next=%d\n",L.r[i].otheritems,L.r[i].next);
}
}

void Sort(SLList L,int adr[]) // 改此句(類型)
{ // 求得adr[1..L.length]，adr[i]為靜態鏈表L的第i個最小記錄的序號
int i=1,p=L.r[0].next;
while(p)
{
adr[i++]=p;
p=L.r[p].next;
}
}

void Rearrange(SLList &L,int adr[]) // 改此句(類型)
{ // adr給出靜態鏈表L的有序次序，即L.r[adr[i]]是第i小的記錄。
// 本演算法按adr重排L.r，使其有序。演算法10.18(L的類型有變)
int i,j,k;
for(i=1;i<L.recnum;++i) // 改此句(類型)
if(adr[i]!=i)
{
j=i;
L.r[0]=L.r[i]; // 暫存記錄L.r[i]
while(adr[j]!=i)
{ // 調整L.r[adr[j]]的記錄到位直到adr[j]=i為止
k=adr[j];
L.r[j]=L.r[k];
adr[j]=j;
j=k; // 記錄按序到位
}
L.r[j]=L.r[0];
adr[j]=j;
}
}

#define N 10
void main()
{
RedType d[N]={{278,1},{109,2},{63,3},{930,4},{589,5},{184,6},{505,7},{269,8},{8,9},{83,10}};
SLList l;
int *adr;
InitList(l,d,N);
printf("排序前(next域還沒賦值):\n");
print(l);
RadixSort(l);
printf("排序後(靜態鏈表):\n");
print(l);
adr=(int*)malloc((l.recnum)*sizeof(int));
Sort(l,adr);
Rearrange(l,adr);
printf("排序後(重排記錄):\n");
print(l);
}
/*******************************************/
//歸並排序
#include<stdio.h>
typedef int InfoType; // 定義其它數據項的類型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項，具體類型在主程中定義
};

struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
void Merge(RedType SR[],RedType TR[],int i,int m,int n)
{ // 將有序的SR[i..m]和SR[m+1..n]歸並為有序的TR[i..n] 演算法10.12
int j,k,l;
for(j=m+1,k=i;i<=m&&j<=n;++k) // 將SR中記錄由小到大地並入TR
if LQ(SR[i].key,SR[j].key)
TR[k]=SR[i++];
else
TR[k]=SR[j++];
if(i<=m)
for(l=0;l<=m-i;l++)
TR[k+l]=SR[i+l]; // 將剩餘的SR[i..m]復制到TR
if(j<=n)
for(l=0;l<=n-j;l++)
TR[k+l]=SR[j+l]; // 將剩餘的SR[j..n]復制到TR
}

void MSort(RedType SR[],RedType TR1[],int s, int t)
{ // 將SR[s..t]歸並排序為TR1[s..t]。演算法10.13
int m;
RedType TR2[MAXSIZE+1];
if(s==t)
TR1[s]=SR[s];
else
{
m=(s+t)/2; // 將SR[s..t]平分為SR[s..m]和SR[m+1..t]
MSort(SR,TR2,s,m); // 遞歸地將SR[s..m]歸並為有序的TR2[s..m]
MSort(SR,TR2,m+1,t); // 遞歸地將SR[m+1..t]歸並為有序的TR2[m+1..t]
Merge(TR2,TR1,s,m,t); // 將TR2[s..m]和TR2[m+1..t]歸並到TR1[s..t]
}
}

void MergeSort(SqList &L)
{ // 對順序表L作歸並排序。演算法10.14
MSort(L.r,L.r,1,L.length);
}

void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}

#define N 7
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
MergeSort(l);
printf("排序後:\n");
print(l);
}
/**********************************************/
//起泡排序
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函數結果狀態代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
typedef int Boolean;
#define N 8
void bubble_sort(int a[],int n)
{ // 將a中整數序列重新排列成自小至大有序的整數序列(起泡排序)
int i,j,t;
Status change;
for(i=n-1,change=TRUE;i>1&&change;--i)
{
change=FALSE;
for(j=0;j<i;++j)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
change=TRUE;
}
}
}

void print(int r[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",r[i]);
printf("\n");
}

void main()
{
int d[N]={49,38,65,97,76,13,27,49};
printf("排序前:\n");
print(d,N);
bubble_sort(d,N);
printf("排序後:\n");
print(d,N);
}
/****************************************************/
//簡單選擇排序
#include<stdio.h>
typedef int InfoType; // 定義其它數據項的類型
#define MAXSIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項，具體類型在主程中定義
};

struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
int SelectMinKey(SqList L,int i)
{ // 返回在L.r[i..L.length]中key最小的記錄的序號
KeyType min;
int j,k;
k=i; // 設第i個為最小
min=L.r[i].key;
for(j=i+1;j<=L.length;j++)
if(L.r[j].key<min) // 找到更小的
{
k=j;
min=L.r[j].key;
}
return k;
}

void SelectSort(SqList &L)
{ // 對順序表L作簡單選擇排序。演算法10.9
int i,j;
RedType t;
for(i=1;i<L.length;++i)
{ // 選擇第i小的記錄，並交換到位
j=SelectMinKey(L,i); // 在L.r[i..L.length]中選擇key最小的記錄
if(i!=j)
{ // 與第i個記錄交換
t=L.r[i];
L.r[i]=L.r[j];
L.r[j]=t;
}
}
}

void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}

#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
SelectSort(l);
printf("排序後:\n");
print(l);
}
/************************************************/
//樹形選擇排序
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函數結果狀態代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函數的類型,其值是函數結果狀態代碼，如OK等
typedef int Boolean; // Boolean是布爾類型,其值是TRUE或FALSE
typedef int InfoType; // 定義其它數據項的類型
#define MAXSIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項，具體類型在主程中定義
};

struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
void TreeSort(SqList &L)
{ // 樹形選擇排序
int i,j,j1,k,k1,l,n=L.length;
RedType *t;
l=(int)ceil(log(n)/log(2))+1; // 完全二叉樹的層數
k=(int)pow(2,l)-1; // l層完全二叉樹的結點總數
k1=(int)pow(2,l-1)-1; // l-1層完全二叉樹的結點總數
t=(RedType*)malloc(k*sizeof(RedType)); // 二叉樹採用順序存儲結構
for(i=1;i<=n;i++) // 將L.r賦給葉子結點
t[k1+i-1]=L.r[i];
for(i=k1+n;i<k;i++) // 給多餘的葉子的關鍵字賦無窮大
t[i].key=INT_MAX;
j1=k1;
j=k;
while(j1)
{ // 給非葉子結點賦值
for(i=j1;i<j;i+=2)
t[i].key<t[i+1].key?(t[(i+1)/2-1]=t[i]):(t[(i+1)/2-1]=t[i+1]);
j=j1;
j1=(j1-1)/2;
}
for(i=0;i<n;i++)
{
L.r[i+1]=t[0]; // 將當前最小值賦給L.r[i]
j1=0;
for(j=1;j<l;j++) // 沿樹根找結點t[0]在葉子中的序號j1
t[2*j1+1].key==t[j1].key?(j1=2*j1+1):(j1=2*j1+2);
t[j1].key=INT_MAX;
while(j1)
{
j1=(j1+1)/2-1; // 序號為j1的結點的雙親結點序號
t[2*j1+1].key<=t[2*j1+2].key?(t[j1]=t[2*j1+1]):(t[j1]=t[2*j1+2]);
}
}
free(t);
}

void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}

#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
TreeSort(l);
printf("排序後:\n");
print(l);
}
/****************************/
//堆排序
#include<stdio.h>
typedef int InfoType; // 定義其它數據項的類型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項，具體類型在主程中定義
};

struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};

typedef SqList HeapType; // 堆採用順序表存儲表示
void HeapAdjust(HeapType &H,int s,int m) // 演算法10.10
{ // 已知H.r[s..m]中記錄的關鍵字除H.r[s].key之外均滿足堆的定義，本函數
// 調整H.r[s]的關鍵字,使H.r[s..m]成為一個大頂堆(對其中記錄的關鍵字而言)
RedType rc;
int j;
rc=H.r[s];
for(j=2*s;j<=m;j*=2)
{ // 沿key較大的孩子結點向下篩選
if(j<m&<(H.r[j].key,H.r[j+1].key))
++j; // j為key較大的記錄的下標
if(!LT(rc.key,H.r[j].key))
break; // rc應插入在位置s上
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc; // 插入
}

void HeapSort(HeapType &H)
{ // 對順序表H進行堆排序。演算法10.11
RedType t;
int i;
for(i=H.length/2;i>0;--i) // 把H.r[1..H.length]建成大頂堆
HeapAdjust(H,i,H.length);
for(i=H.length;i>1;--i)
{ // 將堆頂記錄和當前未經排序子序列H.r[1..i]中最後一個記錄相互交換
t=H.r[1];
H.r[1]=H.r[i];
H.r[i]=t;
HeapAdjust(H,1,i-1); // 將H.r[1..i-1]重新調整為大頂堆
}
}

void print(HeapType H)
{
int i;
for(i=1;i<=H.length;i++)
printf("(%d,%d)",H.r[i].key,H.r[i].otherinfo);
printf("\n");
}

#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
HeapType h;
int i;
for(i=0;i<N;i++)
h.r[i+1]=d[i];
h.length=N;
printf("排序前:\n");
print(h);
HeapSort(h);
printf("排序後:\n");
print(h);
}

㈢ 計算機演算法中的遞歸法與選擇排序法是什麼請細講

遞歸是設計和描述演算法的一種有力的工具，由於它在復雜演算法的描述中被經常採用，為此在進一步介紹其他演算法設計方法之前先討論它。
能採用遞歸描述的演算法通常有這樣的特徵：為求解規模為N的問題，設法將它分解成規模較小的問題，然後從這些小問題的解方便地構造出大問題的解，並且這些規模較小的問題也能採用同樣的分解和綜合方法，分解成規模更小的問題，並從這些更小問題的解構造出規模較大問題的解。特別地，當規模N=1時，能直接得解。

遞歸演算法的執行過程分遞推和回歸兩個階段。在遞推階段，把較復雜的問題（規模為n）的求解推到比原問題簡單一些的問題（規模小於n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是說，為計算fib(n)，必須先計算fib(n-1)和fib(n-2)，而計算fib(n-1)和fib(n-2)，又必須先計算fib(n-3)和fib(n-4)。依次類推，直至計算fib(1)和fib(0)，分別能立即得到結果1和0。在遞推階段，必須要有終止遞歸的情況。例如在函數fib中，當n為1和0的情況。
在回歸階段，當獲得最簡單情況的解後，逐級返回，依次得到稍復雜問題的解，例如得到fib(1)和fib(0)後，返回得到fib(2)的結果，……，在得到了fib(n-1)和fib(n-2)的結果後，返回得到fib(n)的結果。
在編寫遞歸函數時要注意，函數中的局部變數和參數知識局限於當前調用層，當遞推進入「簡單問題」層時，原來層次上的參數和局部變數便被隱蔽起來。在一系列「簡單問題」層，它們各有自己的參數和局部變數。
由於遞歸引起一系列的函數調用，並且可能會有一系列的重復計算，遞歸演算法的執行效率相對較低。當某個遞歸演算法能較方便地轉換成遞推演算法時，通常按遞推演算法編寫程序。例如上例計算斐波那契數列的第n項的函數fib(n)應採用遞推演算法，即從斐波那契數列的前兩項出發，逐次由前兩項計算出下一項，直至計算出要求的第n項。

選擇排序法 是對 定位比較交換法 的一種改進。在講選擇排序法之前我們先來了解一下定位比較交換法。為了便於理解，設有10個數分別存在數組元素a[0]～a[9]中。定位比較交換法是由大到小依次定位a[0]～a[9]中恰當的值（和武林大會中的比武差不多），a[9]中放的自然是最小的數。如定位a[0],先假定a[0]中當前值是最大數，a[0]與後面的元素一一比較，如果a[4]更大，則將a[0]、a[4]交換，a[0]已更新再與後面的a[5]～a[9]比較，如果a[8]還要大，則將a[0]、a[8]交換，a[0]又是新數，再與a[9]比較。一輪比完以後，a[0]就是最大的數了，本次比武的武狀元誕生了，接下來從a[1]開始，因為狀元要休息了，再來一輪a[1]就是次大的數，也就是榜眼，然後從a[2]開始，比出探花，真成比武大會了，當必到a[8]以後，排序就完成了。
下面給大家一個例子：
mai()
{
int a[10];
int i,j,t;
for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*輸入10個數，比武報名，報名費用10000￥ ^_^*/
for ( i = 0; i < 9; i ++ )
for ( j = i + 1; j < 10; j ++)
if ( a[ i ] < a[ j ] ) { t = a[ i ]; a[ i ] = a[ j ]; a[ j ] = t; } /*打不過就要讓出頭把交椅，不過a[ i ]比較愛面子，不好意思見 a[ j ]，讓t幫忙*/
for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /*顯示排序後的結果*/
}
好啦，羅嗦了半天總算把定位比較排序法講完了，這個方法不錯，容易理解，就是有點麻煩，一把椅子換來換去，哎～
所以就有了下面的選擇排序法，開始的時候椅子誰也不給，放在一邊讓大家看著，找個人k記錄比賽結果，然後發椅子。具體來講呢就是，改進定位比較排序法，但是這個改進只是一部分，比較的次數沒變，該怎麼打還是怎麼打，就是不用換椅子了。每次外循環先將定位元素的小標i值記錄到K，認為a[k]是最大元素其實i=k還是a[ i ]最大，a[k]與後面的元素一一比較，該交換的也是也不換，就是把K的值改變一下就完了，最後在把a[k]與a[ i ]交換，這樣a就是最大的元素了。然後進入下一輪的比較。選擇排序法與定位比較排序法相比較，比的次數沒變，交換的次數減少了。
下面也寫個例子：
main()
{
int a[10];
int i,j,t,k;
for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*輸入10個數，比武報名，報名費用10000￥ ^_^*/
for ( i = 0; i < 9; i ++ )
{ k = i; /*裁判AND記者實時追蹤報道比賽情況*/
for ( j = i + 1; j < 10; j ++)
if ( a[ k ] < a[ j ] ) k = j;
t = a[ i ]; a[ i ] = a[ k ]; a[ k ] = t; /* t 發放獎品*/
}
for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /*顯示排序後的結果*/
}

㈣ 計算機第八講 怎樣研究演算法 排序演算法研究示例

排序的演算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序演算法。這裡面插入排序和冒泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間

㈤ 計算機的排序演算法有幾種

這基礎的排序演算法有很多，有二分排序法屬性排序法，冒泡排序法

㈥ 快速排序

快速排序（Quicksort），計算機科學詞彙，適用領域Pascal，c++等語言，是對冒泡排序演算法的一種改進。

1、首先設定一個分界值，通過該分界值將數組分成左右兩部分。

2、將大於或等於分界值的數據集中到數組右邊，小於分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小於分界值，而右邊部分中各元素都大於或等於分界值。

3、然後，左邊和右邊的數據可以獨立排序。對於左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。

4、重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成後，整個數組的排序也就完成了。

排序演示

假設一開始序列{xi}是：5，3，7，6，4，1，0，2，9，10，8。

此時，ref=5，i=1，j=11，從後往前找，第一個比5小的數是x8=2，因此序列為：2，3，7，6，4，1，0，5，9，10，8。

此時i=1，j=8，從前往後找，第一個比5大的數是x3=7，因此序列為：2，3，5，6，4，1，0，7，9，10，8。

此時，i=3，j=8，從第8位往前找，第一個比5小的數是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。

此時，i=3，j=7，從第3位往後找，第一個比5大的數是x4=6，因此：2，3，0，5，4，1，6，7，9，10，8。

此時，i=4，j=7，從第7位往前找，第一個比5小的數是x6=1，因此：2，3，0，1，4，5，6，7，9，10，8。

此時，i=4，j=6，從第4位往後找，直到第6位才有比5大的數，這時，i=j=6，ref成為一條分界線，它之前的數都比它小，之後的數都比它大，對於前後兩部分數，可以採用同樣的方法來排序。

㈦ 數據結構的排序方法有哪些

題目似乎不是很完整。
先回答：（1）C，（2）A，（3）D，(4)B，(5)G
(1) C．插入排序 法從未排序的序列中依次取出元素，與已排序序列(初始時為空)中的元素作比較，將其放入已排序序列的正確位置上；
(2) A．選擇排序 法從未排序的序列中挑選元素， 並將其依次放入已排序序列(初始時為空)的一端；交換排序方法是對序列中的元素進行一系列比較， 當被比較的兩元素逆序時，進行交換；
(3) D．起泡排序 和 （4）B．快速排序 是基於這類方法的兩種排序方法；
(5) G．堆排序 法是基於選擇排序的一種排序方法，是完全二叉樹結構的一個重要應用。

原題應該是：
排序方法有許多種，（1）法從未排序的序列中依次取出元素，與已排序序列（初始時為空）中的元素作比較，將其放入已排序序列的正確位置上；（2）法從未排序的序列中挑選元素，並將其依次放入已排序序列（初始時為空）的一端； 交換排序方法是對序列中的元素進行一系列比較，當被比較的兩元素逆序時，進行交換；（3）和（4）是基於這類方法的兩種排序方法， 而（4）是比（3）效率更高的方法；（5）法是基於選擇排序的一種排序方法，是完全二叉樹結構的一個重要應用。 【北方交通大學 1999 一、3 （5分）】
（1）--（5）: A．選擇排序 B．快速排序 C．插入排序 D．起泡排序
E．歸並排序 F．shell排序 G．堆排序 H．基數排序
【解答】（1）C，（2）A，（3）D，(4)B，(5)G

㈧ O（n2）排序演算法的總結

最近在慕課網上學習了O（n2）時間復雜度的相關演算法，總算是對這些演算法的優缺點有了詳細的特點。其實對於任何的演算法，沒有優點和缺點，而是有相應的特點。所以我們應該結合不同的排序環境來選擇不同的排序演算法，從而達到在實現時間和執行效率上的平衡。這是因為，越是簡單的排序演算法，實現起來肯定是越容易，而且出現BUG的概率也不會太大。相反，復雜演算法可能效率更高，但是出現問題的可能性也會更大。下面，我就結合O（n2）時間復雜度的四個經典排序演算法，為您詳細講解這四個演算法的特點。

定義：選擇排序（Selection sort）是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。

圖示說明：

源碼實現：

分析：通過選擇排序的圖示和源碼我們可以看出來，選擇排序要進行兩次循環，而且最關鍵的是內層循環在每一次執行時都是全部執行完的。那我們有沒有辦法讓內層循環不用每次都執行完呢？方法肯定是有的，這就是冒泡排序。

定義：冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序演算法。它重復地走訪過要排序的元素列，一次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到沒有相鄰元素需要交換，也就是說該元素已經排序完成。

圖示說明：

源碼實現：

分析：從圖示和源碼可以看出來，從執行次數上來說，冒泡排序是比選擇排序的循環次數更少的。那是不是就可以說，如果待排序的數組中元素比較合適，冒泡排序在時間復雜度上是不是會比選擇排序更好呢？真的是這樣的嗎？

其實不是的，經過多次測試驗證，冒泡排序基本上是比選擇排序的時間復雜度要差的，這是為什麼呢？從源碼中我們可以很明顯的看出來，雖然冒泡排序是比選擇排序執行次數少了，但是交換的次數明顯增多了，而如果你對計算機程序指令的實現原理只要有一個基本的認識，就應該知道交換動作比賦值動作是需要更多指令操作的。所以說，最終冒泡排序大部分情況下，比選擇排序的時間復雜度都要高。

既然交換動作這么消耗資源，那有沒有一種方法，即能夠減少內層循環的執行次數，又可以減少甚至是無需交換操作呢？這就要請出插入排序了。

定義：插入排序（Insertion Sort）的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，即每步將一個待排序的記錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。

圖示說明：

源碼實現：

分析：從圖示和源碼可以看出來，插入排序（優化後的）是沒有交換操作的，而且對於內層循環來說，如果待排序的元素是比較大的值，那內層循環執行的次數會非常的少。因此，如果原始數據基本上是有序的，那使用插入排序的效率會非常的高。在O（n2）級別的排序演算法還可以再優化嗎？如果可以從哪裡優化呢？下面我們來介紹希爾排序，正是這個排序演算法的提出，使得排序演算法打破了O（n2）時間復雜度的禁錮。

定義：希爾排序(Shell's Sort)是插入排序的一種又稱「縮小增量排序」（Diminishing Increment Sort），是直接插入排序演算法的一種更高效的改進版本。該演算法的基本思想是：把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，排序演算法便終止。

對於希爾排序來說，最關鍵的就是增量該如何選取。這個增量該怎麼確定，這還真是個數學難題，至今沒有解答。但是通過大量的實驗，還是有個經驗值的。我們的例子給出的增量選取公式是：h = 3 * h + 1，下面請看圖示說明。

圖示說明：

源碼實現：

分析：從插入排序中我們知道，插入排在待排序數組基本有序時，插入排序的演算法效率會非常高，所以我們可以這樣認為，希爾排序的最終思想就是：先將整個待排記錄序列分割成為若乾子序列分別進行直接插入排序，待整個序列中的記錄「基本有序」時，在對全體進行一次直接插入排序。

而希爾排序的效率之所以很高，就是因為這個基本思想確實很有用：即當h值大的時候，數據項每一趟排序需要移動元素的個數很少，但數據項移動的距離很長。這是非常有效率的。而當h減小時，每一趟排序需要移動的元素的個數增多，但是此時數據項已經接近於它們排序後最終的位置，這對於插入排序可以更有效率。正是這兩種情況的結合才使希爾排序效率那麼高。

對於增量的選取，可以稱得上是一種魔法。在希爾的原稿中，他建議初始的間距為N/2，簡單地把每一趟排序分成了兩半。但是，這被證明並不是最好的數列。盡管對於大多數的數據來說這個方法還是比插入排序效果好，但是這種方法有時會使運行時間降到O(N2)，這並不比插入排序的效率更高。間隔序列中的數字互質通常被認為很重要：也就是說，除了1之外它們沒有公約數。這個約束條件使每一趟排序更有可能保持前一趟排序已排好的效果。希爾最初以N/2為間隔的低效性就是歸咎於它沒有遵守這個准則。

總結：上面就是四種經典O（n2）級別排序演算法的相關說明。其實在各種場合下選擇排序和冒泡排序基本上是不會使用的，因為使用場景基本沒有。而對於插入排序和希爾排序來說，在待排序數據基本有序的情況下，使用場景還是有的，比如一些日誌文件中存儲的日誌，可能大部分的日誌記錄都是基於時間排序，只是在某些極端情況下導致一些日誌晚存儲了導致時間不一致。

我是徐建航， 這是我寫的第31篇文章，歡迎你加入007社群，七天寫一篇，一起寫七年，七年之後一起去南極。

㈨ 計算機經典演算法——錦標賽排序演算法

關鍵詞 ：二叉樹
生活中的淘汰錦標賽 ：在單淘汰的錦標賽中，選手們兩兩比賽，勝者晉級，敗者被淘汰。比如世界乒乓球錦標賽或者大滿貫網球賽就是這么進行的。
這樣一來，就可以把比賽的賽程和結果對應成一個二叉樹。在樹中每一個選手是二叉樹中的一個葉子結點，每一場比賽就相當於兩個數字在比大小，數字大的選手獲勝進入下一輪，成為樹幹上的根。所以，進入到某一輪比賽的選手，其實都是某個子數乾的根結點。最後的冠軍就是整個二叉樹的根結點。這種賽制的合理性需要一個假設：A>B, B>C --> 必然有A>C（輸贏的傳遞性）

工程中，要比較兩個數字的大小
第一步：把所有的數字放到二叉樹的葉子節點，然後按照錦標賽單淘汰的方式，兩兩比較選出最大
第二步：對於第二大的，從所有被最大的數字淘汰的數字中選擇，以此類推選擇對於第三、第四大的數字

假定有25名短跑選手比賽競爭金銀銅牌，賽場上有5條賽道，因此一次可以有5個人同時比賽。比賽不及時，只看相應的名次。假如選手的發揮是穩定的，也就是說如果約翰比張三跑的快，張三比凱利跑的快，那麼約翰一定比凱利跑得快。最少需要幾組比賽才能決出前3名？

第一步，將25名選手分成5組，每組5人。讓每個組分別比賽，排出各組的名次來，假設他們的名字就是他們在小組中的編號。

第二步，讓各組的第一名，也就是A1、B1、C1、D1、E1再比一次。假設A1在這次比賽中獲勝，這樣我們就知道了第一名。

第四步，如上圖通過8次（5 +1 + 1 +1）選出的5人進行第三名的比賽，前3全部產生

更好的答案：
前6次比賽都是必須的，最佳答案的前2步和上述方案中的前2步是相同的。在第6組比賽（即5個第一名的比賽）結束之後，最後的2名已經沒有資格角逐前3名了。

不妨假設那一次比賽從最快到最慢的結果是A1、B1、C1、D1、E1，在D1和E1之前已經有3名選手了，他們肯定不是前3名。
誰還會是第二名的候選呢？根據錦標賽排序的原則，直接輸給第一名的人，也就是A2，以及最後附加賽輸給他的B1，僅此兩人而已。
誰會是第三名的候選呢？和A1在某一組比賽的第三名，他們是A3、C1，或者輸給第二名候選人B1的人，即B2。

因此，第二、第三名的候選人一共只有5個， A2、A3、B1、B2和C1，剛好湊一組。這樣加上前6次，只需要賽7組，這是最佳方法。

註：來自吳軍老師得到課程