交換排序：冒泡排序 （ 相鄰比序法 ）(穩(wěn)定)
冒泡排序是一種簡(jiǎn)單的交換類(lèi)排序方法拨扶，它是通過(guò)相鄰的數(shù)據(jù)元素的交換屈雄，逐步將待排序序列變成有序序列的過(guò)程官套。
【 算法思想 】 反復(fù)掃描待排序記錄序列，在掃描的過(guò)程中順次比較相鄰的兩個(gè)元素的大小惋嚎，若逆序就交換位置站刑。
以升序?yàn)槔?br> 在第一趟冒泡排序中，從第一個(gè)記錄開(kāi)始摆尝，掃描整個(gè)待排序記錄序列因悲，若相鄰的兩個(gè)記錄逆序晃琳，則交換位置。在掃描的過(guò)程中卫旱，不斷地將相鄰兩個(gè)記錄中關(guān)鍵字大的記錄向后移動(dòng)顾翼，最后必然將待排序記錄序列中的最大關(guān)鍵字記錄換到待排序記錄序列的末尾，這也是最大關(guān)鍵字記錄應(yīng)在的位置灸芳。然后進(jìn)行第二趟冒泡排序取逾，對(duì)前 n-1 個(gè)記錄進(jìn)行同樣的操作，其結(jié)果是使次大的記錄被放在第 n-1 個(gè)記錄的位置上。
然后進(jìn)行第三趟冒泡排序晴埂，對(duì)前 n-2 個(gè)記錄進(jìn)行同樣的操作，其結(jié)果是使第三大的記錄被放在第 n-2 個(gè)記錄的位置上精耐。
如此反復(fù)琅锻，每一趟冒泡排序都將一個(gè)記錄排到位，直到剩下一個(gè)最小的記錄惊完。
若在某一趟冒泡排序過(guò)程中处硬，沒(méi)有發(fā)現(xiàn)一個(gè)逆序荷辕，則可直接結(jié)束整個(gè)排序過(guò)程，所以 冒泡過(guò)程最多進(jìn)行 n-1 趟疮方。
C#實(shí)現(xiàn)：
冒泡排序版本1：（未考慮骡显，已經(jīng)有序后，外部循環(huán)的中止承边，外部循環(huán)會(huì)有多余循環(huán)）
public class ChangeSort
{
/// <summary>
/// 冒泡排序 版本1：(沒(méi)有考慮如果已經(jīng)有序了的情況)
/// </summary>
public static void BubbleSort_1(int[] a)
{
int len = a.Length;
int temp = 0;
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
Debug.Log("版本1：內(nèi)部循環(huán)次數(shù)");
}
Debug.Log("版本1：外部循環(huán)次數(shù)");
Utilit.Print(a, i);
}
}
}
冒泡排序版本2：考慮的外循環(huán)的終止博助，但內(nèi)循環(huán)次數(shù)還可以有更大的減少
public class ChangeSort
{
/// <summary>
/// 冒泡排序 版本2：（避免有序后依然進(jìn)行排序痹愚，減少了外循環(huán)次數(shù),但沒(méi)有考慮后方已經(jīng)有序的情況，例如：[4,3,2,1,0,5,6,7,8,9]）
/// </summary>
/// <param name="a"></param>
public static void BubbleSort_2(int[] a)
{
int len = a.Length;
int temp = 0;
bool exchang = false; //標(biāo)志位：是否有逆序相鄰數(shù)
for (int i = 0; i < len; i++)
{
exchang = false;
for (int j = 0; j < len-1 - i; j++)
{
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
exchang = true;
}
Debug.Log("版本2：內(nèi)部循環(huán)次數(shù)");
}
if (!exchang)
{
break;
}
Debug.Log("版本2：外部循環(huán)次數(shù)");
Utilit.Print(a, i);
}
}
}
冒泡排序版本3：進(jìn)一步減少內(nèi)部循環(huán)次數(shù)
public class ChangeSort
{
/// <summary>
/// 冒泡排序 版本3：（考慮后方已經(jīng)有序的情況，例如：[4,3,2,1,0,5,6,7,8,9]动壤，減少了內(nèi)部的循環(huán)次數(shù)）
/// </summary>
/// <param name="a"></param>
public static void BubbleSort_3(int[] a)
{
int len = a.Length;
int temp = 0;
int lastExchangIndex = 0;//記錄最后發(fā)生交換的索引
int sortBorder = len - 1; //無(wú)序數(shù)的邊界索引
bool exchang = false; //標(biāo)志位：是否有逆序相鄰數(shù)
for (int i = 0; i < len; i++)
{
exchang = false;
for (int j = 0; j < sortBorder; j++)
{
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
exchang = true;
lastExchangIndex = j;
}
Debug.Log("版本3：內(nèi)部循環(huán)次數(shù)");
}
sortBorder = lastExchangIndex;
if (!exchang)
{
break;
}
Debug.Log("版本3：外部循環(huán)次數(shù)");
Utilit.Print(a, i);
}
}
}
測(cè)試用例：
using UnityEngine;
public class _014_ChangeSort : MonoBehaviour
{
void Start()
{
int[] a = Utilit.RandArray(20, 10);//new int[] { 4,3,2,1,0,5,6,7,8,9};
int[] b = (int[])a.Clone();
int[] c = (int[])a.Clone();
Debug.Log("---------------冒泡排序 版本1--------------");
ChangeSort.BubbleSort_1(a);
Debug.Log("---------------冒泡排序 版本2--------------");
ChangeSort.BubbleSort_2(b);
Debug.Log("---------------冒泡排序 版本3--------------");
ChangeSort.BubbleSort_3(c);
}
}
測(cè)試結(jié)果：
注：
算法的時(shí)間復(fù)雜度為 O(n ^2 )阁簸，
空間復(fù)雜度為 O(1)启妹。
另外，冒泡排序法是一種穩(wěn)定的排序方法桨啃。
