綜合排序演算法

1. 排序方法有哪幾種排序方法的相關知識

1、排序方法有10種，分別是：冒泡排序、選擇排序、插入排序、希爾排序、歸並排序、快速排序、堆排序、計數排序、桶排序、基數排序。
2、冒泡排序演算法是把較小的元素往前調或者把較大的元素往後調。這種方法主要是通過對相鄰兩個元素進行大小的比較，根據比較結果和演算法規則對該二元素的位置進行交換，這樣逐個依次進行比較和交換，就能達到排序目的。
3、選擇排序演算法的基本思路是為每一個位置選擇當前最小的元素。選擇排序的基本思想是，基於直接選擇排序和堆排序這兩種基本的簡單排序方法。
4、插入排序演算法是基於某序列已經有序排列的情況下，通過一次插入一個元素的方式按照原有排序方式增加元素。

2. 淘寶商品綜合排序什麼演算法

商品綜合排序跟10項因素相關，具體如下
影響寶貝排名的重要因素的權重佔比：
成交量：15%
好評率：10%
收藏量：8%
上下架：12%
轉化率：14%
櫥窗推薦：10%
回購率：10%
DSR：8% 賣家服務評級系統(Detail Seller Rating）

3. 排序方法有哪幾種

排序方法有：

一、直接插入排序

原理：從待排序的數中選出一個來，插入到前面的合適位置。

二、選擇排序

與直接插入排序正好相反，選擇排序是從待排序的數中選出最小的放在已經排好的後面，這個演算法選數耗時。

三、快速排序

快速排序簡稱快排，是一種比較快的排序，適合基本無序的數據，為什麼這么說呢？下面我說下快排的思路：設置兩個指針：i和j，分別指向第一個和最後一個，i像後移動，j向前移動，選第一個數為標准（一般這樣做，當然快排的關鍵就是這個「標准」的選取），從後面開始。

找到第一個比標准小的數，互換位置，然後再從前面，找到第一個比標准大的數，互換位置，第一趟的結果就是標准左邊的都小於標准，右邊的都大於標准（但不一定有序），分成兩撥後，繼續遞歸的使用上述方法，最終有序！

四、冒泡排序

冒泡排序是一種很簡單，不論是理解還是時間起來都比較容易的一種排序演算法，思路簡單：小的數一點一點向前起泡，最終有序。

五、歸並排序

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

首先考慮下如何將將二個有序數列合並。這個非常簡單，只要從比較二個數列的第一個數，誰小就先取誰，取了後就在對應數列中刪除這個數。然後再進行比較，如果有數列為空，那直接將另一個數列的數據依次取出即可。

4. C語言 排序演算法綜合系統

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<iostream>
using namespace std;
void find(int *a,int n);
void input(int pIn[], int n);
void del(int *a,int n);
void Swap(int *a, int *b);
int Partition(int a[], int p, int r);
void arrange(int *c,int length);
template <class Type>
/* 為了便於維護，現在把排序封裝在類ArraySort內
*/
class ArraySort
{
private: int elem; //elem的值決定按升序還是降序
int len; //排序數組的長度
Type *b; //排序時用與交換的數組
Type *a; //用來存放要排序的數組；
public:
void set(Type c[],int k); //接收要排序的數組及數組長度
void Sort(); //進行排序
void MergeSort(int ,int );
void Merge(int ,int ,int); //進行合並
void Copy(int ,int); //復制一個數組到另一個數組
void ArPrint(); //輸出數組元素
void ReturnCopy(Type c[]); //把已經排序數組返回給原數組
~ArraySort();
ArraySort(int k=0){
elem=k;
len=0;
a=NULL;
b=NULL;
}
};
template<class Type>
void ArraySort<Type>::set(Type c[],int k )
{ int m;
len=k;
//len=c.length;
a=new Type[len];
b=new Type[len];
if((a==NULL)||(b==NULL))
{ cout<<"can't allocate more memory,terminating."<<endl;
exit(1);
}
else{
for(int i=0;i<len;i++)
a[i]=c[i];
}
cout<<" input the number 0 or 1:"<<endl;
cout<<"0 min to max:"<<endl;
cout<<"1 max to min"<<endl;
cin>>m;
if(m>=0&&m<=1)
elem=m;
else {
cout<<"You input a illegal number!!";
cout<<" input the number 0 or 1:"<<endl;
cout<<"0 min to max:"<<endl;
cout<<"1 max to min"<<endl;
}
}
template <class Type>
void ArraySort<Type>::Sort()
{
MergeSort(0,len-1);
}
template <class Type>
void ArraySort<Type>::Merge(int left,int m,int right)
{
int i=left,
j=m+1,
k=left;
if(elem==0){
while((i<=m)&&(j<=right))
if(a[i]<=a[j]) b[k++]=a[i++];
else b[k++]=a[j++];
}
else{
while((i<=m)&&(j<=right))
if(a[i]>=a[j]) b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<=m)
b[k++]=a[i++];
while(j<=right)
b[k++]=a[j++];
}
template <class Type>
void ArraySort<Type>::Copy(int left,int right)
{
for(int i=left;i<=right;i++)
a[i]=b[i];
}
template <class Type>
void ArraySort<Type>::ArPrint()
{
// int len=this.a.length;
cout<<"The length of array is :"<<len<<endl;
cout<<"The elements of array is :"<<endl;
for(int i=0;i<len;i++)
cout<<" "<<a[i];
if(i/5==0)
cout<<endl;
}
template <class Type>
void ArraySort<Type>::MergeSort(int left,int right)
{
if(left<right){
int i=(left+right)/2;
MergeSort(left,i);
MergeSort(i+1,right);
Merge(left,i,right);
Copy(left,right);
}
}
template <class Type>
void ArraySort<Type>::ReturnCopy(Type c[])
{
for(int i=0;i<len;i++)
c[i]=a[i];
}
template <class Type>
ArraySort<Type>::~ArraySort()
{
delete a;
delete b;
}

void qSort(int pIn[], int p/*0*/, int r/*r = N - 1*/);
main()
{ char c;
int i,a[12]={6,11,12,5,1,13,8,9,14,7,10},exit=1;
do
{
system("cls");
for(i=0;i<80;i++)
printf("*");
printf("\t 1:選擇排序法\n");
printf("\t 2:冒泡排序法\n");
printf("\t 3:插入排序法\n");
printf("\t 4:合並排序法\n");
printf("\t 5:退出\n");
printf("\t 請選擇輸入選項【1\\2\\3\\4\\5】:\n");
do
{
c=getch();
}while(c!='1'&&c!='2'&&c!='3'&&c!='4'&&c!='5');

switch(c)
{ case '1':input(a,11);
cout<<endl;
for(i=0;i<11;i++)
cout<<a[i]<<" ";
cout<<endl;
break;
case '2':del(a,11);
cout<<endl;
for(i=0;i<11;i++)
cout<<a[i]<<" ";
cout<<endl;break;
case '3':find(a,11); break;
case '4':arrange(a,11); break;
case '5':exit=0;
}
printf("按任意鍵返回主菜單:\n");
getche();

}while(exit);
}
void input(int pIn[], int n)
{
qSort(pIn, 0, n-1);
}
void Swap(int *a, int *b){
int c = *a;
*a = *b;
*b = c;
}

int Partition(int a[], int p, int r)
{
int i = p;
int j = r + 1;
int x = a[p];

while(1){
while (i <= r && a[++i] < x); // 如果你要從大到小排序就改x前的<為>
while (j >= p && a[--j] > x); //同時這的>也要改為<
if (i >= j) break;
Swap(&a[i], &a[j]);
}

if (i == j) {
j --;
}

a[p] = a[j];
a[j] = x;
return j;
}

void qSort(int pIn[], int p/*0*/, int r/*r = N - 1*/)
{
if (p < r) {
int q = Partition(pIn, p, r);
qSort(pIn, p, q - 1);
qSort(pIn, q + 1, r);
}
}
void del(int *a,int n)//冒泡
{
int i,j,k;
for(i=0;i<=n-2;i++)
for(j=0;j<=n-2-i;j++)
if(a[j]>a[j+1])//如果你要從大到小排序就改>為<
{
k=a[j];
a[j]=a[j+1];
a[j+1]=k;
}
}

void find(int *a,int n)//插入
{
int i, j, x;
for(i = 1;i < n;i++)
{
x = a[i];
j = i - 1;

while(j >= 0 && a[j] > x){
a[j+1] = a[j];
j--;
}

a[j+1] = x;
}
for(i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
void arrange(int *c,int length)//組合
{
int i;

ArraySort<int > as;
as.set(c,length);
cout<<"排序前的數組元素序列："<<endl;
for( i=0;i<length;i++)
cout<<" "<<c[i];
cout<<endl;
as.Sort();

as.ReturnCopy(c);

cout<<"排序後的數組元素序列："<<endl;
for( i=0;i<length;i++)
cout<<" "<<c[i];
cout<<endl;
}
樓主做了我2個多小時啊。。TC不能識別有的頭文件哈，我已經用VC6.0測試過了

5. 常用的數據排序演算法有哪些,各有什麼特點舉例結合一種排序演算法並應用數組進行數據排序。

排序簡介
排序是數據處理中經常使用的一種重要運算,在計算機及其應用系統中,花費在排序上的時間在系統運行時間中佔有很大比重;並且排序本身對推動演算法分析的發展也起很大作用。目前已有上百種排序方法，但尚未有一個最理想的盡如人意的方法，本章介紹常用的如下排序方法，並對它們進行分析和比較。

1、插入排序（直接插入排序、折半插入排序、希爾排序）；
2、交換排序（起泡排序、快速排序）；
3、選擇排序（直接選擇排序、堆排序）；
4、歸並排序；
5、基數排序；

學習重點
1、掌握排序的基本概念和各種排序方法的特點，並能加以靈活應用；
2、掌握插入排序(直接插入排序、折半插入排序、希爾排序)、交換排序（起泡排序、快速排序）、選擇排序（直接選擇排序、堆排序）、二路歸並排序的方法及其性能分析方法；
3、了解基數排序方法及其性能分析方法。

排序（sort）或分類

所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。其確切定義如下：
輸入：n個記錄R1，R2，…，Rn，其相應的關鍵字分別為K1，K2，…，Kn。
輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

1．被排序對象--文件
被排序的對象--文件由一組記錄組成。
記錄則由若干個數據項(或域)組成。其中有一項可用來標識一個記錄，稱為關鍵字項。該數據項的值稱為關鍵字(Key)。
注意：
在不易產生混淆時，將關鍵字項簡稱為關鍵字。

2．排序運算的依據--關鍵字
用來作排序運算依據的關鍵字，可以是數字類型，也可以是字元類型。
關鍵字的選取應根據問題的要求而定。
【例】在高考成績統計中將每個考生作為一個記錄。每條記錄包含准考證號、姓名、各科的分數和總分數等項內容。若要惟一地標識一個考生的記錄，則必須用"准考證號"作為關鍵字。若要按照考生的總分數排名次，則需用"總分數"作為關鍵字。

排序的穩定性

當待排序記錄的關鍵字均不相同時，排序結果是惟一的，否則排序結果不唯一。
在待排序的文件中，若存在多個關鍵字相同的記錄，經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩定的；若具有相同關鍵字的記錄之間的相對次序發生變化，則稱這種排序方法是不穩定的。
注意：
排序演算法的穩定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得演算法不滿足穩定性要求，則該排序演算法就是不穩定的。

排序方法的分類

1．按是否涉及數據的內、外存交換分
在排序過程中，若整個文件都是放在內存中處理，排序時不涉及數據的內、外存交換，則稱之為內部排序(簡稱內排序)；反之，若排序過程中要進行數據的內、外存交換，則稱之為外部排序。
注意：
① 內排序適用於記錄個數不很多的小文件
② 外排序則適用於記錄個數太多，不能一次將其全部記錄放人內存的大文件。

2．按策略劃分內部排序方法
可以分為五類：插入排序、選擇排序、交換排序、歸並排序和分配排序。

排序演算法分析

1．排序演算法的基本操作
大多數排序演算法都有兩個基本的操作：
(1) 比較兩個關鍵字的大小；
(2) 改變指向記錄的指針或移動記錄本身。
注意：
第(2)種基本操作的實現依賴於待排序記錄的存儲方式。

2．待排文件的常用存儲方式
（1） 以順序表(或直接用向量)作為存儲結構
排序過程：對記錄本身進行物理重排（即通過關鍵字之間的比較判定，將記錄移到合適的位置）

（2） 以鏈表作為存儲結構
排序過程：無須移動記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈式)排序；

（3） 用順序的方式存儲待排序的記錄，但同時建立一個輔助表(如包括關鍵字和指向記錄位置的指針組成的索引表)
排序過程：只需對輔助表的表目進行物理重排（即只移動輔助表的表目，而不移動記錄本身）。適用於難於在鏈表上實現，仍需避免排序過程中移動記錄的排序方法。

3．排序演算法性能評價
（1） 評價排序演算法好壞的標准
評價排序演算法好壞的標准主要有兩條：
① 執行時間和所需的輔助空間
② 演算法本身的復雜程度

（2） 排序演算法的空間復雜度
若排序演算法所需的輔助空間並不依賴於問題的規模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。
非就地排序一般要求的輔助空間為O(n)。

（3） 排序演算法的時間開銷
大多數排序演算法的時間開銷主要是關鍵字之間的比較和記錄的移動。有的排序演算法其執行時間不僅依賴於問題的規模，還取決於輸入實例中數據的狀態。

文件的順序存儲結構表示

#define n l00 //假設的文件長度，即待排序的記錄數目
typedef int KeyType； //假設的關鍵字類型
typedef struct{ //記錄類型
KeyType key； //關鍵字項
InfoType otherinfo；//其它數據項，類型InfoType依賴於具體應用而定義
}RecType；
typedef RecType SeqList[n+1]；//SeqList為順序表類型，表中第0個單元一般用作哨兵
注意：
若關鍵字類型沒有比較算符，則可事先定義宏或函數來表示比較運算。
【例】關鍵字為字元串時，可定義宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那麼演算法中"a<b"可用"LT(a，b)"取代。若使用C++，則定義重載的算符"<"更為方便。

按平均時間將排序分為四類：

（1）平方階(O(n2))排序
一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序；

（2）線性對數階(O(nlgn))排序
如快速、堆和歸並排序；

（3）O(n1+￡)階排序
￡是介於0和1之間的常數，即0<￡<1，如希爾排序；

（4）線性階(O(n))排序
如桶、箱和基數排序。

各種排序方法比較

簡單排序中直接插入最好，快速排序最快，當文件為正序時，直接插入和冒泡均最佳。

影響排序效果的因素

因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法應綜合考慮下列因素：
①待排序的記錄數目n；
②記錄的大小(規模)；
③關鍵字的結構及其初始狀態；
④對穩定性的要求；
⑤語言工具的條件；
⑥存儲結構；
⑦時間和輔助空間復雜度等。

不同條件下，排序方法的選擇

(1)若n較小(如n≤50)，可採用直接插入或直接選擇排序。
當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少於直接插人，應選直接選擇排序為宜。
(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜；
(3)若n較大，則應採用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸並排序。
快速排序是目前基於比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
堆排序所需的輔助空間少於快速排序，並且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的。
若要求排序穩定，則可選用歸並排序。但本章介紹的從單個記錄起進行兩兩歸並的 排序演算法並不值得提倡，通常可以將它和直接插入排序結合在一起使用。先利用直接插入排序求得較長的有序子文件，然後再兩兩歸並之。因為直接插入排序是穩定的，所以改進後的歸並排序仍是穩定的。

4)在基於比較的排序方法中，每次比較兩個關鍵字的大小之後，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程。
當文件的n個關鍵字隨機分布時，任何藉助於"比較"的排序演算法，至少需要O(nlgn)的時間。
箱排序和基數排序只需一步就會引起m種可能的轉移，即把一個記錄裝入m個箱子之一，因此在一般情況下，箱排序和基數排序可能在O(n)時間內完成對n個記錄的排序。但是，箱排序和基數排序只適用於像字元串和整數這類有明顯結構特徵的關鍵字，而當關鍵字的取值范圍屬於某個無窮集合(例如實數型關鍵字)時，無法使用箱排序和基數排序，這時只有藉助於"比較"的方法來排序。
若n很大，記錄的關鍵字位數較少且可以分解時，採用基數排序較好。雖然桶排序對關鍵字的結構無要求，但它也只有在關鍵字是隨機分布時才能使平均時間達到線性階，否則為平方階。同時要注意，箱、桶、基數這三種分配排序均假定了關鍵字若為數字時，則其值均是非負的，否則將其映射到箱(桶)號時，又要增加相應的時間。
(5)有的語言(如Fortran，Cobol或Basic等)沒有提供指針及遞歸，導致實現歸並、快速(它們用遞歸實現較簡單)和基數(使用了指針)等排序演算法變得復雜。此時可考慮用其它排序。
(6)本章給出的排序演算法，輸人數據均是存儲在一個向量中。當記錄的規模較大時，為避免耗費大量的時間去移動記錄，可以用鏈表作為存儲結構。譬如插入排序、歸並排序、基數排序都易於在鏈表上實現，使之減少記錄的移動次數。但有的排序方法，如快速排序和堆排序，在鏈表上卻難於實現，在這種情況下，可以提取關鍵字建立索引表，然後對索引表進行排序。然而更為簡單的方法是：引人一個整型向量t作為輔助表，排序前令t[i]=i(0≤i<n)，若排序演算法中要求交換R[i]和R[j]，則只需交換t[i]和t[j]即可；排序結束後，向量t就指示了記錄之間的順序關系：
R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
若要求最終結果是：
R[0].key≤R[1].key≤…≤R[n-1].key
則可以在排序結束後，再按輔助表所規定的次序重排各記錄，完成這種重排的時間是O(n)。

6. 綜合排序演算法的比較

#include "stdio.h "
#include "stdlib.h "
#define Max 100 //假設文件長度
typedef struct{ //定義記錄類型
int key; //關鍵字項
}RecType;
typedef RecType SeqList[Max+1]; //SeqList為順序表，表中第0個元素作為哨兵
int n; //順序表實際的長度
//==========直接插入排序法======
void InsertSort(SeqList R) { //對順序表R中的記錄R[1¨n]按遞增序進行插入排序
int i,j;
for(i=2;i <=n;i++) //依次插入R[2]，……，R[n]
if(R[i].key <R[i-1].key){ //若R[i].key大於等於有序區中所有的keys，則R[i]留在原位 R[0]=R[i];j=i-1; //R[0]是R[i]的副本 do { //從右向左在有序區R[1¨i-1]中查找R[i] 的位置 R[j+1]=R[j]; //將關鍵字大於R[i].key的記錄後移 j--; }while(R[0].key <R[j].key); //當R[i].key≥R[j].key 是終止
R[j+1]=R[0]; //R[i]插入到正確的位置上
}//endif
}
//==========冒泡排序======= typedef enum{FALSE,TRUE} Boolean; //FALSE為0，TRUE為1
void BubbleSort(SeqList R) { //自下向上掃描對R做冒泡排序
int i,j;
bool exchange; //交換標志 for(i=1;i <n;i++) { //最多做n-1趟排序
exchange=false; //本趟排序開始前，交換標志應為假
for(j=n-1;j> =i;j--){ //對當前無序區R[i¨n] 自下向上掃描
if(R[j+1].key <R[j].key){ //兩兩比較，滿足條件交換記錄
R[0]=R[j+1]; //R[0]不是哨兵，僅做暫存單元
R[j+1]=R[j];
R[j]=R[0];
exchange=true; //發生了交換，故將交換標志置為真
}
if(! exchange) return; //本趟排序未發生交換，提前終止演算法
}// endfor（為循環）
}
//==========快速排序=======
//1.========一次劃分函數=====
int Partition(SeqList R,int i,int j) {
// 對R[i¨j]做一次劃分，並返回基準記錄的位置
RecType pivot=R[i]; //用第一個記錄作為基準
while(i <j) { //從區間兩端交替向中間掃描，直到i=j
while(i <j &&R[j].key> =pivot.key) //基準記錄pivot相當與在位置i上
j--; //從右向左掃描，查找第一個關鍵字小於pivot.key的記錄R[j]
if(i <j) //若找到的R[j].key < pivot.key，則
R[i++]=R[j]; //交換R[i]和R[j]，交換後i指針加1
while(i <j &&R[i].key <=pivot.key) //基準記錄pivot相當與在位置j上
i++; //從左向右掃描，查找第一個關鍵字小於pivot.key的記錄R[i]
if(i <j) //若找到的R[i].key > pivot.key，則
R[j--]=R[i]; //交換R[i]和R[j]，交換後j指針減1
}
R[i]=pivot; //此時，i=j，基準記錄已被最後定位
return i; //返回基準記錄的位置
}
//2.=====快速排序===========
void QuickSort(SeqList R,int low,int high) { //R[low..high]快速排序
int pivotpos; //劃分後基準記錄的位置
if(low <high) { //僅當區間長度大於1時才排序
pivotpos=Partition(R,low,high); //對R[low..high]做一次劃分，得到基準記錄的位置
QuickSort(R,low,pivotpos-1); //對左區間遞歸排序
QuickSort(R,pivotpos+1,high); //對右區間遞歸排序
}
}
//======直接選擇排序========
void SelectSort(SeqList R) {
int i,j,k;
for(i=1;i <n;i++){ //做第i趟排序（1≤i≤n-1）
k=i;
for(j=i+1;j <=n;j++) //在當前無序區R[i¨n]中選key最小的記錄R[k]
if(R[j].key <R[k].key)
k=j; //k記下目前找到的最小關鍵字所在的位置
if(k!=i) { //交換R[i]和R[k]
R[0]=R[i];R[i]=R[k];R[k]=R[0];
} //endif
} //endfor
}
//======堆排序========
//==========大根堆調整函數=======
void Heapify(SeqList R,int low,int high) {
// 將R[low..high]調整為大根堆，除R[low]外，其餘結點均滿足堆性質
int large; //large指向調整結點的左、右孩子結點中關鍵字較大者
RecType temp=R[low]; //暫存調整結點
for(large=2*low; large <=high;large*=2){ //R[low]是當前調整結點
//若large> high,則表示R[low]是葉子，調整結束；否則先令large指向R[low]的左孩子
if(large <high && R[large].key <R[large+1].key)
large++; //若R[low]的右孩子存在且關鍵字大於左兄弟，則令large指向它
//現在R[large]是調整結點R[low]的左右孩子結點中關鍵字較大者
if(temp.key> =R[large].key) //temp始終對應R[low]
break; //當前調整結點不小於其孩子結點的關鍵字，結束調整
R[low]=R[large]; //相當於交換了R[low]和R[large]
low=large; //令low指向新的調整結點，相當於temp已篩下到large的位置
}
R[low]=temp; //將被調整結點放入最終位置上
}
//==========構造大根堆==========
void BuildHeap(SeqList R) { //將初始文件R[1..n]構造為堆
int i;
for(i=n/2;i> 0;i--)
Heapify(R,i,n); //將R[i..n]調整為大根堆
}
//==========堆排序===========
void HeapSort(SeqList R) { //對R[1..n]進行堆排序，不妨用R[0]做暫存單元
int i;
BuildHeap(R); //將R[1..n]構造為初始大根堆
for(i=n;i> 1;i--){ //對當前無序區R[1..i]進行堆排序，共做n-1趟。
R[0]=R[1]; R[1]=R[i];R[i]=R[0]; //將堆頂和堆中最後一個記錄交換
Heapify(R,1,i-1); //將R[1..i-1]重新調整為堆，僅有R[1]可能違反堆性質。
}
}
//==========二路歸並排序===========
//===將兩個有序的子序列R[low..m]和R[m+1..high]歸並成有序的序列R[low..high]===
void Merge(SeqList R,int low,int m,int high) {
int i=low,j=m+1,p=0; //置初始值
RecType *R1; //R1為局部量
R1=(RecType *)malloc((high-low+1)*sizeof(RecType)); //申請空間
while(i <=m && j <=high) //兩個子序列非空時取其小者輸出到R1[p]上
R1[p++]=(R[i].key <=R[j].key)? R[i++]:R[j++];
while(i <=m) //若第一個子序列非空，則復制剩餘記錄到R1
R1[p++]=R[i++];
while(j <=high) //若第二個子序列非空，則復制剩餘記錄到R1中
R1[p++]=R[j++];
for(p=0,i=low;i <=high;p++,i++)
R[i]=R1[p]; //歸並完成後將結果復制回R[low..high]
}
//=========對R[1..n]做一趟歸並排序========
void MergePass(SeqList R,int length) {
int i;
for(i=1;i+2*length-1 <=n;i=i+2*length)
Merge(R,i,i+length-1,i+2*length-1); //歸並長度為length的兩個相鄰的子序列
if(i+length-1 <n) //尚有一個子序列，其中後一個長度小於length
Merge(R,i,i+length-1,n); //歸並最後兩個子序列
//注意：若i≤n且i+length-1≥n時，則剩餘一個子序列輪空，無須歸並
}
//========== 自底向上對R[1..n]做二路歸並排序===============
void MergeSort(SeqList R) {
int length;
for(length=1;length <n;length*=2) //做[lgn]趟排序
MergePass(R,length); //有序長度≥n時終止
}
//==========輸入順序表========
void input_int(SeqList R) {
int i;
printf( "Please input num(int): ");
scanf( "%d ",&n);
printf( "Plase input %d integer: ",n);
for(i=1;i <=n;i++)
scanf( "%d ",&R[i].key);
}
//==========輸出順序表========
void output_int(SeqList R) {
int i;
for(i=1;i <=n;i++)
printf( "%4d ",R[i].key);
}
//==========主函數======
void main() {
int i;
SeqList R;
input_int(R);
printf( "\t******** Select **********\n ");
printf( "\t1: Insert Sort\n ");
printf( "\t2: Bubble Sort\n ");
printf( "\t3: Quick Sort\n ");
printf( "\t4: Straight Selection Sort\n ");
printf( "\t5: Heap Sort\n ");
printf( "\t6: Merge Sort\n ");
printf( "\t7: Exit\n ");
printf( "\t***************************\n ");
scanf( "%d ",&i); //輸入整數1-7，選擇排序方式
switch (i){
case 1: InsertSort(R);
break; //值為1，直接插入排序
case 2: BubbleSort(R);
break; //值為2，冒泡法排序
case 3: QuickSort(R,1,n);
break; //值為3，快速排序
case 4: SelectSort(R);
break; //值為4，直接選擇排序
case 5: HeapSort(R);
break; //值為5，堆排序
case 6: MergeSort(R);
break; //值為6，歸並排序
case 7: exit(0); //值為7，結束程序
}
printf( "Sort reult: ");
output_int(R);
}

7. 數據結構課程設計的各種排序演算法的綜合比較 哪位大神幫寫一下~

排序法
平均時間
最差情形
穩定度
額外空間
備注
冒泡
O(n2)
O(n2)
穩定
O(1)
n小時較好
交換
O(n2)
O(n2)
不穩定
O(1)
n小時較好
選擇
O(n2)
O(n2)
不穩定
O(1)
n小時較好
插入
O(n2)
O(n2)
穩定
O(1)
大部分已排序時較好
基數
O(logRB)
O(logRB)
穩定
O(n)
B是真數(0-9)，R是基數(個十百)
Shell
O(nlogn)
O(ns)
1<s<2
不穩定
O(1)
s是所選分組
快速
O(nlogn)
O(n2)
不穩定
O(nlogn)
n大時較好
歸並
O(nlogn)
O(nlogn)
穩定
O(1)
n大時較好
堆
O(nlogn)
O(nlogn)
不穩定
O(1)
n大時較好

8. 排序演算法有多少種

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

9. 試說明對長度為n的元素表進行綜合並排序,時間復雜度是如何計算的

"綜合並排序"是什麼意思？
分析執行過程
for(int i=0;i<n;i++) {}
是o(n)
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {}
} 是o(n2)
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
for(int k=0;k<n;k++) {}
}
} 是o(n3)
for(int i=0;i<n;i++) {}
for(int j=0;j<n;j++) {}
是o(n)
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {}
}
for(int j=0;j<n;j++) {}
是o(n2)
也就是不管平行的循環有多少，只管嵌套最深的那個循環有幾層
============================================================
分析一下歸並排序的時間復雜度，一趟歸並需要將SR[1]～SR[n]中相鄰的長度為h的有序序列進行兩兩歸並。並將結果放到TR1[1]～TR1[n]中，這需要將待排序序列中的所有記錄掃描一遍，因此耗費O(n)時間，而由完全二叉樹的深度可知，整個歸並排序需要進行.log2n.次，因此，總的時間復雜度為O(nlogn)，而且這是歸並排序演算法中最好、最壞、平均的時間性能。
由於歸並排序在歸並過程中需要與原始記錄序列同樣數量的存儲空間存放歸並結果以及遞歸時深度為log2n的棧空間，因此空間復雜度為O(n+logn)，也就是O(n)。

10. 常用的排序演算法都有哪些

排序演算法 所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
分類
在計算機科學所使用的排序演算法通常被分類為：
計算的復雜度（最差、平均、和最好表現），依據串列（list）的大小（n）。一般而言，好的表現是O。(n log n)，且壞的行為是Ω(n2)。對於一個排序理想的表現是O(n)。僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要Ω(n log n)。
記憶體使用量（以及其他電腦資源的使用）
穩定度：穩定排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。也就是一個排序演算法是穩定的，就是當有兩個有相等關鍵的紀錄R和S，且在原本的串列中R出現在S之前，在排序過的串列中R也將會是在S之前。
一般的方法：插入、交換、選擇、合並等等。交換排序包含冒泡排序（bubble sort）和快速排序（quicksort）。選擇排序包含shaker排序和堆排序（heapsort）。
當相等的元素是無法分辨的，比如像是整數，穩定度並不是一個問題。然而，假設以下的數對將要以他們的第一個數字來排序。
(4, 1) (3, 1) (3, 7) (5, 6)
在這個狀況下，有可能產生兩種不同的結果，一個是依照相等的鍵值維持相對的次序，而另外一個則沒有：
(3, 1) (3, 7) (4, 1) (5, 6) (維持次序)
(3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)
不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地時作為穩定。作這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個物件間之比較，就會被決定使用在原先資料次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。
排列演算法列表
在這個表格中，n是要被排序的紀錄數量以及k是不同鍵值的數量。
穩定的
冒泡排序（bubble sort） — O(n2)
雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 額外 記憶體
計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外 記憶體
歸並排序 （merge sort）— O(n log n); 需要 O(n) 額外記憶體
原地歸並排序 — O(n2)
二叉樹排序 （Binary tree sort） — O(n log n); 需要 O(n) 額外記憶體
鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外記憶體
基數排序 （radix sort）— O(n·k); 需要 O(n) 額外記憶體
Gnome sort — O(n2)
Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外記憶體
不穩定
選擇排序 （selection sort）— O(n2)
希爾排序 （shell sort）— O(n log n) 如果使用最佳的現在版本
Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n) 期望時間, O(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情況時間, 需要 額外的 O(n + k) 空間, 也需要找到最長的遞增子序列（longest increasing subsequence）
不實用的排序演算法
Bogo排序 — O(n × n!) 期望時間, 無窮的最壞情況。
Stupid sort — O(n3); 遞回版本需要 O(n2) 額外記憶體
Bead sort — O(n) or O(√n), 但需要特別的硬體
Pancake sorting — O(n), 但需要特別的硬體
排序的演算法
排序的演算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序演算法。這裡面插入排序和冒泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在一個較小范圍內的排序演算法。
插入排序
冒泡排序
選擇排序
快速排序
堆排序
歸並排序
基數排序
希爾排序
插入排序
插入排序是這樣實現的：
首先新建一個空列表，用於保存已排序的有序數列（我們稱之為"有序列表"）。
從原數列中取出一個數，將其插入"有序列表"中，使其仍舊保持有序狀態。
重復2號步驟，直至原數列為空。
插入排序的平均時間復雜度為平方級的，效率不高，但是容易實現。它藉助了"逐步擴大成果"的思想，使有序列表的長度逐漸增加，直至其長度等於原列表的長度。
冒泡排序
冒泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重復2號步驟，直至再也不能交換。
冒泡排序的平均時間復雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的：
設數組內存放了n個待排數字，數組下標從1開始，到n結束。
i=1
從數組的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n－1演算法結束，否則回到第3步
選擇排序的平均時間復雜度也是O(n²)的。
快速排序
現在開始，我們要接觸高效排序演算法了。實踐證明，快速排序是所有排序演算法中最高效的一種。它採用了分治的思想：先保證列表的前半部分都小於後半部分，然後分別對前半部分和後半部分排序，這樣整個列表就有序了。這是一種先進的思想，也是它高效的原因。因為在排序演算法中，演算法的高效與否與列表中數字間的比較次數有直接的關系，而"保證列表的前半部分都小於後半部分"就使得前半部分的任何一個數從此以後都不再跟後半部分的數進行比較了，大大減少了數字間不必要的比較。但查找數據得另當別論了。
堆排序
堆排序與前面的演算法都不同，它是這樣的：
首先新建一個空列表，作用與插入排序中的"有序列表"相同。
找到數列中最大的數字，將其加在"有序列表"的末尾，並將其從原數列中刪除。
重復2號步驟，直至原數列為空。
堆排序的平均時間復雜度為nlogn,效率高（因為有堆這種數據結構以及它奇妙的特徵，使得"找到數列中最大的數字"這樣的操作只需要O(1)的時間復雜度，維護需要logn的時間復雜度），但是實現相對復雜（可以說是這里7種演算法中比較難實現的）。
看起來似乎堆排序與插入排序有些相像，但他們其實是本質不同的演算法。至少，他們的時間復雜度差了一個數量級，一個是平方級的，一個是對數級的。
平均時間復雜度
插入排序 O(n2)
冒泡排序 O(n2)
選擇排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
歸並排序 O(n log n)
基數排序 O(n)
希爾排序 O(n1.25)
冒泡排序
654
比如說這個，我想讓它從小到大排序，怎麼做呢？
第一步：6跟5比，發現比它大，則交換。564
第二步：5跟4比，發現比它大，則交換。465
第三步：6跟5比，發現比它大，則交換。456