排序算法中的穩(wěn)定和不穩(wěn)定指的是什么？
成都創(chuàng)新互聯(lián)公司長(zhǎng)期為上1000+客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為鹽池企業(yè)提供專業(yè)的網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)，鹽池網(wǎng)站改版等技術(shù)服務(wù)。擁有十載豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。
若在待排序的紀(jì)錄中，存在兩個(gè)或兩個(gè)以上的關(guān)鍵碼值相等的紀(jì)錄，經(jīng)排序后這些記錄的相對(duì)次序仍然保持不變，則稱相應(yīng)的排序方法是穩(wěn)定的方法，否則是不穩(wěn)定的方法。
根據(jù)排序過程中涉及的存儲(chǔ)器不同，可以講排序方法分為兩大類：一類是內(nèi)部排序，指的是待排序的幾率存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器中進(jìn)行的排序過程；另一類的外部排序，指的是排序中要對(duì)外存儲(chǔ)器進(jìn)行訪問的排序過程。
內(nèi)部排序是排序的基礎(chǔ)，在內(nèi)部排序中，根據(jù)排序過程中所依據(jù)的原則可以將它們分為5類：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序；
根據(jù)排序過程的時(shí)間復(fù)雜度來分，可以分為三類：簡(jiǎn)單排序、先進(jìn)排序、基數(shù)排序。
評(píng)價(jià)排序算法優(yōu)劣的標(biāo)準(zhǔn)主要是兩條：一是算法的運(yùn)算量，這主要是通過記錄的比較次數(shù)和移動(dòng)次數(shù)來反應(yīng)；另一個(gè)是執(zhí)行算法所需要的附加存儲(chǔ)單元的的多少。
插入排序：
有一個(gè)已經(jīng)有序的數(shù)據(jù)序列，要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一個(gè)數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個(gè)時(shí)候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為O(n^2)。是穩(wěn)定的排序方法。插入算法把要排序的數(shù)組分成兩部分：第一部分包含了這個(gè)數(shù)組的所有元素，但將最后一個(gè)元素除外（讓數(shù)組多一個(gè)空間才有插入的位置），而第二部分就只包含這一個(gè)元素（即待插入元素）。在第一部分排序完成后，再將這個(gè)最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步將一個(gè)待排序的紀(jì)錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上，直到全部插入完為止。
重慶分公司
重慶分公司
void InsertSort(int *arr, size_t size)
{
assert(arr);
for (int i = 0; i < size - 1; ++i)
{
int tmp = arr[i+1];
int end = i;
while (end >= 0&&arr[end]>tmp)
{
arr[end + 1] = arr[end];
--end;
}
arr[end + 1] = tmp;//即使都大于tmp,將tmp放置arr[0]處
}
}希爾排序：
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。
希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。
希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率。
但插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位。
先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分組。所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2
< 
…
void ShellSort(int *arr, size_t size)
{
assert(arr);
int gap = size;
while (gap>1)//注意跳出條件
{
gap = gap / 3 + 1;
for (int i = 0; i < size - gap; ++i)//i可取到size-1-gap
{
int tmp = arr[i + gap];
int end = i;
while (end >= 0 && arr[end]>tmp)
{
arr[end + gap] = arr[end];
end-=gap;
}
arr[end + gap] = tmp;//即使都大于tmp,將tmp放置arr[0]處
}
}
}選擇排序：
選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。
n個(gè)記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果：
①初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空。
②第1趟排序
在無序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的第1個(gè)記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)。
……
③第i趟排序
第i趟排序開始時(shí)，當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個(gè)記錄R交換，使R[1..i]和R分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)。
思路：對(duì)比數(shù)組中前一個(gè)元素跟后一個(gè)元素的大小，如果后面的元素比前面的元素小則用一個(gè)變量k來記住他的位置，接著第二次比較，前面“后一個(gè)元素”現(xiàn)變成了“前一個(gè)元素”，繼續(xù)跟他的“后一個(gè)元素”進(jìn)行比較如果后面的元素比他要小則用變量k記住它在數(shù)組中的位置(下標(biāo))，等到循環(huán)結(jié)束的時(shí)候，我們應(yīng)該找到了最小的那個(gè)數(shù)的下標(biāo)了，然后進(jìn)行判斷，如果這個(gè)元素的下標(biāo)不是第一個(gè)元素的下標(biāo)，就讓第一個(gè)元素跟他交換一下值，這樣就找到整個(gè)數(shù)組中最小的數(shù)了。然后找到數(shù)組中第二小的數(shù)，讓他跟數(shù)組中第二個(gè)元素交換一下值，以此類推。
void SearchSort(int *arr, size_t size)
{
assert(arr);
for (int i = 0,j=size-1; i < j; ++i,-j)
{
int min = i;
int max = j;
for (int k = i; k<=j;++k)
{
if (arr[min]>arr[k])
min = k;
if (arr[max] < arr[k])
max = k;
}
if (min != i)
{
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
if (max == i) //如果最大值在最左邊，肯定要被移走，此時(shí)要轉(zhuǎn)移到相應(yīng)的新位置
{
max = min;
}
}
if (max != j)
{
int tmp = arr[j];
arr[j] = arr[max];
arr[max] = tmp;
}
}
}快速排序：
快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
在c++中可以用函數(shù)qsort（）可以直接為數(shù)組進(jìn)行排序。
用 法:
void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));
參數(shù)：
1 待排序數(shù)組首地址
2 數(shù)組中待排序元素?cái)?shù)量
3 各元素的占用空間大小
4 指向函數(shù)的指針，用于確定排序的順序。
int Quick_Sort(int *arr, int left, int right)
{
assert(arr);
if (left >= right)
return right;
int tmp = arr[right];
int index = right;
--right;
while (left < right)
{
while (left < right&&arr[left] <= tmp)
left++;
while (left < right&&arr[right] >=tmp)
right--;
if (left < right)
swap(arr[left], arr[right]);
}
if (arr[right] >= tmp)
swap(arr[right], arr[index]);//重點(diǎn)
return right;
}
void QuickSort(int* arr,int left,int right)
{
assert(arr);
if (left < right)
{
int mid = Quick_Sort(arr, left, right);
QuickSort(arr, left, mid-1);
QuickSort(arr, mid+1, right);
}
}冒泡排序：
它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。
這個(gè)算法的名字由來是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
冒泡排序算法的運(yùn)作如下：（從后往前）
比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較
void BubbleSort(int* arr, size_t size)
{
assert(arr);
int flag = 0;
for (int i = 0; i < size - 1; ++i)
{
flag = 0;
for (int j = 0; j < size - i - 1;++j)
{
if (arr[j]>arr[j + 1])
{
swap(arr[j], arr[j + 1]);
}
flag = 1;
}
if (flag == 0)
break;
}
}歸并排序：
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。
歸并過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個(gè)有序表中的元素a[i]復(fù)制到r[k]中，并令i和k分別加上1；否則將第二個(gè)有序表中的元素a[j]復(fù)制到r[k]中，并令j和k分別加上1，如此循環(huán)下去，直到其中一個(gè)有序表取完，然后再將另一個(gè)有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)t的單元。歸并排序的算法我們通常用遞歸實(shí)現(xiàn)，先把待排序區(qū)間[s,t]以中點(diǎn)二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]
歸并操作(merge)，也叫歸并算法，指的是將兩個(gè)順序序列合并成一個(gè)順序序列的方法。
如 設(shè)有數(shù)列{6，202，100，301，38，8，1}
初始狀態(tài)：6,202,100,301,38,8，1
第一次歸并后：{6,202},{100,301},{8,38},{1}，比較次數(shù)：3；
第二次歸并后：{6,100,202,301}，{1,8,38}，比較次數(shù)：4；
第三次歸并后：{1,6,8,38,100,202,301},比較次數(shù)：4；
總的比較次數(shù)為：3+4+4=11,；
逆序數(shù)為14；
歸并操作的工作原理如下：
第一步：申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列
第二步：設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
第三步：比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
重復(fù)步驟3直到某一指針超出序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾
/歸并[)升序
//使用鏈表合并思想
void Merge(int* src, int* dest, int begin1, int end1, int begin2, int end2)
{
assert(src&&dest);
int index = begin1;//兩個(gè)區(qū)間挨著
while (begin1 < end1&&begin2 < end2)
{
if (src[begin1] < src[begin2])
{
dest[index++] = src[begin1++];
}
else
{
dest[index++] = src[begin2++];
}
}
if (begin1 < end1)
{
while (begin1 < end1)
dest[index++] = src[begin1++];
}
else
{
while (begin2 < end2)
dest[index++] = src[begin2++];
}
}
void _MergeSort(int* src, int* dst, int left, int right)
{
if (left < right - 1)//[)
{
int mid = left + ((right - left) >> 1);
_MergeSort(src, dst, left, mid);
_MergeSort(src, dst, mid, right);
Merge(src, dst, left, mid, mid, right);
memcpy(src + left, dst + left, sizeof(int)*(right - left));
}
}
void MergeSort(int *a, size_t size)
{
int *dest = new int[size];
_MergeSort(a, dest, 0, 10);
delete[] dest;
}基數(shù)排序：
基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時(shí)間復(fù)雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時(shí)候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。
以LSD為例，假設(shè)原來有一串?dāng)?shù)值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根據(jù)個(gè)位數(shù)的數(shù)值，在走訪數(shù)值時(shí)將它們分配至編號(hào)0到9的桶子中：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接著再進(jìn)行一次分配，這次是根據(jù)十位數(shù)來分配：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
這時(shí)候整個(gè)數(shù)列已經(jīng)排序完畢；如果排序的對(duì)象有三位數(shù)以上，則持續(xù)進(jìn)行以上的動(dòng)作直至最高位數(shù)為止。
//基數(shù)排序：利用哈希桶原理把數(shù)據(jù)排序，可選擇從低位到高位或從高位到低位
//利用稀疏矩陣壓縮存儲(chǔ)進(jìn)行數(shù)據(jù)定位
int GetDigit(int* arr, size_t size)
{
int maxDigit = 1;
int maxNum = 10;
for (int i = 0; i < size; ++i)
{
if (arr[i] >= maxNum)
{
int count = maxDigit;
while (maxNum <= arr[i])
{
maxNum *= 10;
++count;
}
maxDigit = count;
}
}
return maxDigit;
}
void LSDSort(int* arr, size_t size)//從低位開始排 MSD從高位開始排
{
int counts[10] = { 0 };//存位數(shù)對(duì)應(yīng)數(shù)據(jù)個(gè)數(shù)
int startCounts[10] = { 0 };
int *bucket = new int[size];
int digit = 1;//表示先取各位
int maxDigit = GetDigit(arr, size);
int divider = 1;//除數(shù)
while (digit++ <= maxDigit)
{
memset(counts, 0, sizeof(int) * 10);
memset(startCounts, 0, sizeof(int) * 10);
for (int i = 0; i < size; ++i)
counts[(arr[i]/divider)% 10]++;
for (int i = 1; i < 10; ++i)
startCounts[i] = startCounts[i - 1] + counts[i - 1];
for (int i = 0; i < size; ++i)
{
bucket[startCounts[(arr[i] / divider) % 10]++] = arr[i];
}
divider *= 10;
memcpy(arr, bucket, sizeof(int)*size);
}
memcpy(arr, bucket, sizeof(int)*size);
delete[] bucket;
}計(jì)數(shù)排序：
計(jì)數(shù)排序是一個(gè)非基于比較的排序算法，該算法于1954年由 Harold H. Seward 提出。它的優(yōu)勢(shì)在于在對(duì)一定范圍內(nèi)的整數(shù)排序時(shí)，它的復(fù)雜度為Ο(n+k)（其中k是整數(shù)的范圍），快于任何比較排序算法。
計(jì)數(shù)排序?qū)斎氲臄?shù)據(jù)有附加的限制條件：
1、輸入的線性表的元素屬于有限偏序集S；
2、設(shè)輸入的線性表的長(zhǎng)度為n，|S|=k（表示集合S中元素的總數(shù)目為k），則k=O(n)。
在這兩個(gè)條件下，計(jì)數(shù)排序的復(fù)雜性為O(n)。
計(jì)數(shù)排序的基本思想是對(duì)于給定的輸入序列中的每一個(gè)元素x，確定該序列中值小于x的元素的個(gè)數(shù)（此處并非比較各元素的大小，而是通過對(duì)元素值的計(jì)數(shù)和計(jì)數(shù)值的累加來確定）。
void CountSort(int *arr, size_t size,int len)
{
int* bitMap = new int[len];
memset(bitMap, 0, sizeof(int)*len);
for (int i = 0; i < size; ++i)
{
int index = arr[i] >>5;//除以32
int count = arr[i] % 32;
bitMap[index] |= (1 << count);
}
int index = 0;
for (int i = 0; i < len; ++i)
{
int count = 0;
while (count <32&&index
當(dāng)前標(biāo)題：數(shù)據(jù)結(jié)構(gòu)中各種排序的思路
網(wǎng)站鏈接：http://weahome.cn/article/jcpchs.html
