一般码、冒泡排序(Bubble Sort)
算法原理
冒泡排序動畫演示
- 比較相鄰的元素束倍。如果第一個比第二個大被丧，就交換他們兩個。
- 對每一對相鄰元素作同樣的工作绪妹，從開始第一對到結(jié)尾的最后一對甥桂。當(dāng)最后一對執(zhí)行結(jié)束，最后的元素應(yīng)該會是最大的數(shù)邮旷。
- 針對所有的元素重復(fù)以上的步驟黄选，除了最后一個。
- 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較办陷。
算法描述
//將數(shù)組sort進(jìn)行升序排序
public int[] BubbleSort(int [] sort ){
for (int i = 0; i < sort.Length-1; i++) {
for (int j = 0; j < sort.Length - 1 - i; j++) {
//判斷sort[j] 與sort[j+1]比較大小貌夕，如果sort[j]>sort[j+1]則交換位置
if (sort [j] > sort [j + 1]) {
int temp = sort [j];
sort [j] = sort [j+1];
sort [j + 1] = temp;
}
}
}
return sort;
}
二、快速排序(Quick Sort)
算法原理
快速排序動畫演示
- 設(shè)置兩個變量left民镜，right啡专，排序開始的時候：left=0，right=N-1（N為數(shù)組長度）制圈；
- 以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)们童，賦值給key，即key=sort[0]鲸鹦；
- 從right開始向前搜索慧库，即由后開始向前搜索(right--)，找到第一個小于key的值sort[right]馋嗜，將sort[right]和sort[left]互換齐板；
- 從left開始向后搜索，即由前開始向后搜索(left++)葛菇，找到第一個大于key的sort[left]甘磨，將sort[left]和sort[right]互換；
- 重復(fù)第3熟呛、4步宽档，直到left=right尉姨； (3,4步中庵朝，沒找到符合條件的值，即3中sort[right]不小于key,4中sort[left]不大于key的時候改變right又厉、left的值九府，使得right=right-1，left=left+1覆致，直至找到為止侄旬。找到符合條件的值，進(jìn)行交換的時候left煌妈， right位置不變儡羔。另外，left==right這一過程一定正好是left+或right-完成的時候璧诵，此時令循環(huán)結(jié)束）汰蜘。
算法描述
//將數(shù)組sort進(jìn)行升序排序
public void QuickSort (ref int [] sort ,int left,int right){
//當(dāng)left==right時 表示排序結(jié)束
if (left >= right) {
return;
}
int index = QuickSortUnit (ref sort ,left,right)；
QuickSort (ref sort,left,index-1);
QuickSort (ref sort,index+1,right);
}
//將下標(biāo)從left到right的這段數(shù)組進(jìn)行大致排序
public int QuickSortUnit (ref int [] sort ,int left,int right){
int key = sort[left];//將sort[left]賦值給key
while (left < right)
{
//找到后邊第一個大于等于key的值將其與sort[left]交換
while (sort[right] >= key && right > left)
--right;
sort[left] = sort[right];
//找到前邊第一個大于等于key的值將其與sort[right]交換
while (sort[left] <= key && right > left)
++left;
sort[right] = sort[left];
}
//循環(huán)結(jié)束之宿，right = left族操，數(shù)組下標(biāo)小于left的值小于sort[left] ，數(shù)組下標(biāo)大于left的值大于sort[left]
sort[left] = key;
//返回此時的left
return right;
}
三比被、直接插入排序(straight insertion sort)
算法原理
插入排序動畫演示
每步將一個待排序的記錄按其關(guān)鍵字的大小插到前面已經(jīng)排序的序列中的適當(dāng)位置色难，直到全部記錄插入完畢為止泼舱。
算法描述
//將數(shù)組sort進(jìn)行升序排序
public int[] DirectInsertionSort (int [] sort ){
int temp;
for (int i = 1; i < sort.Length; i++) {
if (sort [i] < sort [i - 1]) {
temp = sort [i];
int j = i - 1;
//將有序數(shù)組部分大于temp的值的下標(biāo)往后移一位
while (j>=0 && sort [j] > temp) {
sort [j + 1] = sort [j];
j--;
}
sort [j + 1] = temp;
}
}
return sort;
}
四、希爾排序(Shell Sort)
算法原理
希爾排序動畫演示
- 取一個小于n的整數(shù)d1作為第一個增量枷莉，把文件的全部記錄分組娇昙。所有距離為d1的倍數(shù)的記錄放在同一個組中。
- 在各組內(nèi)進(jìn)行直接插入排序
- 取第二個增量d2<d1重復(fù)上述的分組和排序依沮，直至所取的增量為1即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?/li>
算法描述
public int[] ShellSort (ref int [] sort ){
int k;//設(shè)置增量
for (k = 1; k <= sort.Length / 9; k = 3 * k + 1) {
}
for (; k > 0; k = k / 3) {
//直接插入排序
for (int i = k + 1; i < sort.Length; i += k) {
int temp = sort [i - 1];
int j = i;
while (j > k && sort [j - k - 1] > temp) {
sort [j - 1] = sort [j - k - 1];
j = j - k;
}
sort [j - 1]=temp;
}
}
return sort;
}
五涯贞、直接選擇排序(Straight Selection Sort)
算法原理
選擇排序動畫演示
- 第一次從R[0]~R[n-1]中選取最小值，與R[0]交換
- 第二次從R[1]~R[n-1]中選取最小值危喉，與R[1]交換
- ....
- 第i次從R[i-1]~R[n-1]中選取最小值宋渔，與R[i-1]交換
- .....
- 第n-1次從R[n-2]~R[n-1]中選取最小值，與R[n-2]交換
- 總共通過n-1次辜限，得到一個按排序碼從小到大排列的有序序列·
算法描述
//將數(shù)組sort進(jìn)行升序排序
public int[] StraightSelectSort (ref int [] sort ){
for (int i = 0; i < sort.Length-1; i++) {
int minindex = i;//默認(rèn)此時下標(biāo)為i的值最小
for (int j = i + 1; j < sort.Length; j++) {
if (sort [j] < sort [minindex]) {
minindex = j;//當(dāng)下標(biāo)為j的值小于最小值時將j復(fù)制給minIndex
}
}
//將最小值與sort[i]交換
int temp = sort [i];
sort [i] = sort [minindex];
sort [minindex] = temp;
}
return sort;
}
六皇拣、堆排序(Heap Sort)
算法原理
堆排序動畫演示
- 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區(qū)
- 再將關(guān)鍵字最大的記錄R[1]（即堆頂）和無序區(qū)的最后一個記錄R[n]交換薄嫡，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]氧急，且滿足R[1..n-1].keys≤R[n].key
- 由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆毫深。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換吩坝，由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys哑蔫，同樣要將R[1..n-2]調(diào)整為堆钉寝。
- ……
- 直到無序區(qū)只有一個元素為止。
算法描述
public int[] Heapsort (ref int [] sort ){
int i, size = sort.Length;
//建一個大根堆
for(i=size-1;i>=0;i--)
{
MinHeapify(ref sort,size,i);
}
//將大根堆的根與無序數(shù)組段的最后一個元素交換
while(size>0)
{
sort[size-1]=sort[0]+(sort[0]=sort[size-1])*0;
size--;
MinHeapify(ref sort,size,0);
}
return sort;
}
//建大根堆
public void MinHeapify(ref int [] sort,int size,int element){
int lchild = element*2+1,rchild=lchild+1;
while (rchild < size) {
if(sort[element]<=sort[lchild]&&sort[element]<=sort[rchild])
return;
if (sort [lchild] <= sort [rchild]) {
sort [element] = sort [lchild] + (sort [lchild] = sort [element]) * 0;
element = lchild;
} else {
sort [element] = sort [rchild] + (sort [rchild] = sort [element]) * 0;
element = rchild;
}
lchild=element*2+1;
rchild=lchild+1;
}
}
七闸迷、歸并排序(Merge Sort)
算法原理
歸并排序動畫演示
- 申請空間嵌纲，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
- 設(shè)定兩個指針腥沽，最初位置分別為兩個已經(jīng)排序序列的起始位置
- 比較兩個指針?biāo)赶虻脑卮撸x擇相對小的元素放入到合并空間，并移動指針到下一位置
- 重復(fù)步驟3直到某一指針超出序列尾
- 將另一序列剩下的所有元素直接復(fù)制到合并序列尾
算法描述
public int[] MergeSort(ref int [] sort,ref int [] array,int startIndex,int endIndex ){
int midIndex;
if(startIndex < endIndex)
{
midIndex = (startIndex + endIndex) / 2;
MergeSort(ref sort, ref array, startIndex, midIndex);
MergeSort(ref sort, ref array, midIndex+1, endIndex);
Merge(ref sort, ref array, startIndex, midIndex, endIndex);
}
return sort;
}
public void Merge(ref int[] sort,ref int[] array, int startIndex, int midIndex, int endIndex)
{
int i = startIndex, j=midIndex+1, k = startIndex;
while(i!=midIndex+1 && j!=endIndex+1)
{
if(sort[i] > sort[j])
array[k++] = sort[j++];
else
array[k++] = sort[i++];
}
while(i != midIndex+1)
array[k++] = sort[i++];
while(j != endIndex+1)
array[k++] = sort[j++];
for(i=startIndex; i<=endIndex; i++)
sort[i] = array[i];
} 