幾種排序演算法
1. 排序有幾種方法
一. 冒泡排序
冒泡排序是是一種簡單的排序演算法。它重復地遍歷要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把它們交換過來。遍歷數列的工作是重復的進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端
1.冒泡排序演算法的運作如下：
（1）比較相鄰的元素。如果第一個比第二個大（升序），就交換他們兩個
（2）對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素還是最大的數
（3）針對所有的元素重復以上的步驟，除了最後一個
二. 選擇排序
選擇排序是一種簡單直觀的排序演算法。他的工作原理如下：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置（末尾位置），然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢
選擇排序的主要優點與數據移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，他們當中至少有一個將被移到最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動 元素的排序方法中，選擇排序屬於非常好的一種
三. 插入排序
插入排序是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在從後向前掃描的過程中，需要反復把已排序元素逐步向後挪位，為最新元素提供插入空間
四. 快速排序
快速排序，又稱劃分交換排序。通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都要小，然後再按此方法對兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列
五 希爾排序過程
希爾排序是插入排序的一種，也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。
六. 歸並排序
歸並排序是採用分治法（把復雜問題分解為相對簡單的子問題，分別求解，最後通過組合起子問題的解的方式得到原問題的解）的一個非常典型的應用。歸並排序的思想就是先遞歸分解數組，再合並數組
將數組分解最小之後，然後合並兩個有序數組，基本思路是比較兩個數組的最前面的數，水小九先取誰，取了後相應的指針就往後移一位。然後比較，直至一個數組為空，最後把另一個數組的剩餘部分復制過來即可
2. 幾種常見的排序演算法分析學習
排序演算法一般分為以下幾種： （1）非線性時間比較類排序：交換類排序（快速排序和冒泡排序）、插入類排序（簡單插入排序和希爾排序）、選擇類排序（簡單選擇排序和堆排序）、歸並排序（二路歸並排序和多路歸並排序）；（2）線性時間非比較類排序：計數排序、基數排序和桶排序。
3. 程序的排序演算法都有那幾種
1
插入排序
2快速排序
3選擇排序
4歸並排序
5基數排序
具體的你可以參照以下網址
http://shi..com/shi/233776.html
4. 幾種常見的排序演算法
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];}}}感覺比冒泡法好多啦 //快速排序演算法
5. 以比較為基礎的排序演算法有哪幾種
演算法 優點 缺點
汽泡排序法 對以初步排序的數據來說這種方法的速度很快 在其它情況下運行速度較慢
選擇排序法 非常簡單 對大量數據的排序速度很慢
容易明白
對於少量數據的排序來說速度很快
快速排序法 對大量數據的排序來說速度很快 如果有大量重復的數據就比較麻煩
計數排序法 當數據數值較小(1-1000之間)時，速度非常快 當數據數值較大時，速度較慢
需額外的內存
只能對整數類型的數據排序
6. 計算機的排序演算法有幾種
這基礎的排序演算法有很多，有二分排序法屬性排序法，冒泡排序法
7. 幾種常用的排序演算法比較
排序，從小大，0坐標的在下面，即排序後小的在下面，大的在上面。
1，冒泡Bubble：從第0個開始，一直往上，與相鄰的元素比較，如果下面的大，則交換。
Analysis：
Implementation：
void BubbleSort(int *pData, int iNum)
2，插入Insertion：與打撲克牌時整理牌很想像，假定第一張牌是有序的，從第二張牌開始，拿出這張牌來，往下比較，如果有比這張牌大的，則把它撥到上一個位置，直到找到比手上的這張更小的（或到頂了），
則把手上的這張牌插入到這張更小的牌的後面。
Analysis：
Implementation：
void InsertionSort(int *list, int length)
{
int i, j, temp;
for (i = 1; i < length; i++)
{
temp = list[i];
j = i - 1;
while ((j >= 0) && (list[j] > temp))
{
list[j+1] = list[j];
j--;
}
list[j+1] = temp;
}
}
3，選擇Selection：從所有元素中找到最小的放在0號位置，從其它元素（除了0號元素）中再找到最小的，放到1號位置，......。
Analysis：
Implementation：
void SelectionSort(int data[], int count)
{
int i, j, min, temp;
for (i = 0; i < count - 1; i++)
{
/* find the minimum */
min = i;
for (j = i+1; j < count; j++)
{
if (data[j] < data[min])
{
min = j;
}
}
/* swap data[i] and data[min] */
temp = data[i];
data[i] = data[min];
data[min] = temp;
}
}
4，快速Quick：先拿出中間的元素來（值保存到temp里），設置兩個索引（index or pointer），一個從0號位置開始往最大位置尋找比temp大的元素；一個從最大號位置開始往最小位置尋找比temp小的元素，找到了或到頂了，則將兩個索引所指向的元素
互換，如此一直尋找交換下去，直到兩個索引交叉了位置，這個時候，從0號位置到第二個索引的所有元素就都比temp小，從第一個索引到最大位置的所有元素就都比temp大，這樣就把所有元素分為了兩塊，然後採用前面的辦法分別排序這兩個部分。總的來
說，就是隨機找一個元素（通常是中間的元素），然後把小的放在它的左邊，大的放右邊，對左右兩邊的數據繼續採用同樣的辦法。只是為了節省空間，上面採用了左右交換的方法來達到目的。
Analysis：
Implementation：
void QuickSort(int *pData, int left, int right)
{
int i, j;
int middle, iTemp;
i = left;
j = right;
middle = pData[(left + right) / 2]; //求中間值
do
{
while ((pData[i] < middle) && (i < right)) //從左掃描大於中值的數
i++;
while ((pData[j] > middle) && (j > left)) //從右掃描小於中值的數
j--;
if (i <= j) //找到了一對值
{
//交換
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
} while (i <= j); //如果兩邊掃描的下標交錯，就停止（完成一次）
//當左邊部分有值(left<j)，遞歸左半邊
if(left < j)
QuickSort(pData, left, j);
//當右邊部分有值(right>i)，遞歸右半邊
if(right > i)
QuickSort(pData, i, right);
}
5，希爾Shell：是對Insertion Sort的一種改進，在Insertion Sort中，從第2個位置開始取出數據，每次都是與前一個（step/gap==1）進行比較。Shell Sort修改為，在開始時採用較大的步長step，
從第step位置開始取數據，每次都與它的前step個位置上的數據進行比較（如果有8個數據，初始step==4，那麼pos(4)與pos(0)比較，pos(0)與pos(-4)，pos(5)與pos(1)，pos(1)與pos(-3)，
...... pos(7)與pos(3)，pos(3)與pos(-1)），然後逐漸地減小step，直到step==1。step==1時，排序過程與Insertion Sort一樣，但因為有前面的排序，這次排序將減少比較和交換的次數。
Shell Sort的時間復雜度與步長step的選擇有很大的關系。Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相對比較簡單，它適合
於數據量在5000以下並且速度並不是特別重要的場合。它對於數據量較小的數列重復排序是非常好的。
Analysis：
Implementation：
template<typename RandomIter, typename Compare>
void ShellSort(RandomIter begin, RandomIter end, Compare cmp)
{
typedef typename std::iterator_traits<RandomIter>::value_type value_type;
typedef typename std::iterator_traits<RandomIter>::difference_type diff_t;
diff_t size = std::distance(begin, end);
diff_t step = size / 2;
while (step >= 1)
{
for (diff_t i = step; i < size; ++i)
{
value_type key = *(begin+i);
diff_t ins = i; // current position
while (ins >= step && cmp(key, *(begin+ins-step)))
{
*(begin+ins) = *(begin+ins-step);
ins -= step;
}
*(begin+ins) = key;
}
if(step == 2)
step = 1;
else
step = static_cast<diff_t>(step / 2.2);
}
}
template<typename RandomIter>
void ShellSort(RandomIter begin, RandomIter end)
{
typedef typename std::iterator_traits<RandomIter>::value_type value_type;
ShellSort(begin, end, std::less<value_type>());
}
6，歸並Merge：先將所有數據分割成單個的元素，這個時候單個元素都是有序的，然後前後相鄰的兩個兩兩有序地合並，合並後的這兩個數據再與後面的兩個合並後的數據再次合並，充分前面的過程直到所有的數據都合並到一塊。
通常在合並的時候需要分配新的內存。
Analysis：
Implementation：
void Merge(int array[], int low, int mid, int high)
{
int k;
int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列
int begin1 = low;
int end1 = mid;
int begin2 = mid + 1;
int end2 = high;
for (k = 0; begin1 <= end1 && begin2 <= end2; ++k) //比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置
{
if(array[begin1]<=array[begin2])
{
temp[k] = array[begin1++];
}
else
{
temp[k] = array[begin2++];
}
}
if(begin1 <= end1) //若第一個序列有剩餘，直接拷貝出來粘到合並序列尾
{
memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
}
if(begin2 <= end2) //若第二個序列有剩餘，直接拷貝出來粘到合並序列尾
{
memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
}
memcpy(array+low, temp, (high-low+1)*sizeof(int));//將排序好的序列拷貝回數組中
free(temp);
}
void MergeSort(int array[], unsigned int first, unsigned int last)
{
int mid = 0;
if (first < last)
{
mid = (first+last)/2;
MergeSort(array, first, mid);
MergeSort(array, mid+1,last);
Merge(array,first,mid,last);
}
}
8. 數據結構中幾種常見的排序演算法之比較
冒泡。 復雜度n平方。適用於數組
插入排序。復雜度n平方。適用於鏈表
快排。復雜度nLog(n)。
希爾排序。這是一種插入排序，但是從統計角度看，比插入排序要快。
9. 幾種排序演算法的效率比較
[內部排序的主要演算法及相關可實現程序.rar
] - 內部排序的所有演算法，而且有相關可執行例子，包括插入排序，選擇排序，希爾排序，快速排序，堆排序，歸並排序等，很全，很孀。[排序演算法、字典和B-樹的C++語言實現.zip
] - 排序演算法、字典和B-樹的C++語言實現
代碼內容 包括以下演算法：
qui.c sort: quicksort
qsort.c sort: qsort
ins.c sort: insert sort
shl.c sort: shell sort
has.c dictionary:[幾種排序方法的實現.rar
] - 用 插入排序, 希爾排序 ,冒泡, 快速排序 , 選擇排序 ,堆排序, 歸並排序 實現對任意隨機數序列,並比較各種方法的運行快慢和復雜度[paixu.rar] - 內部排序演算法比較
] - 一個用VC++6.0做的一個資料庫方面的程序，是用來英語學習的，有助於VC資料庫編程的學習。[各種排序方法比較.rar
] - 這個程序包括了各種常用內部排序演算法在平均排序所需時間上的比較.[實現各種排序演算法並分析與比較.rar
] - 本程序實現各種排序演算法並分析與比較 直接插入排序， SHELL排序，冒泡排序，快速排序，簡單選擇排序，堆排序，歸並排序[圖論演算法庫 C++ 語言實現.zip
] - 圖論演算法庫 C++ 語言實現
代碼內容 圖論演算法庫，包括以下演算法：
10. 幾種排序演算法的比較
一、八大排序演算法的總體比較
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個記錄排到位，剩下一個最大記錄直接排在最後；