冒泡排序(從小到大排)
冒泡排序是指比如有n個(gè)數(shù)據(jù),拿第一個(gè)數(shù)據(jù)與剩下的n-1個(gè)數(shù)據(jù)進(jìn)行比較,當(dāng)這個(gè)數(shù)據(jù)比相比較過程中某個(gè)數(shù)據(jù)小就把他們進(jìn)行交換,這樣循環(huán)第一次就會(huì)能將最大的數(shù)據(jù)放到最上面第二輪就會(huì)將第二大的數(shù)據(jù)放到第二的位置上.......,以此循環(huán)下去,
比如有六個(gè)數(shù)據(jù),{1,4,6,23,2,5};
那么模擬一下比較的過程就是
0-1 1-2 2-3 3-4 4-5
0-1 1-2 2-3 3-4
0-1 1-2 2-3
0-1 1-2
0-1
代碼實(shí)現(xiàn):
int a[] = new int[] {1,4,6,23,2,5};
for(int i = 0;i<a.length-1;i++)
{
for(int j = 0;j<a.length-i-1;j++)
{
if(a[j]>a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
選擇排序(從大到小排)
選擇排序是指第一數(shù)與第二數(shù)比較,如果第一個(gè)數(shù)比第二數(shù)小則將第一個(gè)數(shù)與第二個(gè)數(shù)進(jìn)行交換.依次再比較下面的數(shù),這樣一次循環(huán)能將i一個(gè)較大的數(shù)放到相應(yīng)的位置上,所以外層需要循環(huán)n次
如果有六個(gè)數(shù)據(jù){1,4,6,23,2,5}
則是
0-1 1-2 2-3 3-4 4-5
1-2 2-3 3-4 4-5
2-3 3-4 4-5
3-4 4-5
4-5
5
如果出現(xiàn)這種數(shù)據(jù)
{ 1,2,3,4,5,6 }
那么每次都要交換一次,效率很低,所以優(yōu)化一下就是先將較小的數(shù)的下標(biāo)記錄下來當(dāng)外層一次循環(huán)完再進(jìn)行交換
第一層循環(huán)從起始元素開始選到倒數(shù)第二個(gè)元素孤钦，主要是在每次進(jìn)入的第二層循環(huán)之前，將外層循環(huán)的下標(biāo)賦值給臨時(shí)變量晾虑，接下來的第二層循環(huán)中辛臊，如果發(fā)現(xiàn)有比這個(gè)最小位置處的元素更小的元素仙粱，則將那個(gè)更小的元素的下標(biāo)賦給臨時(shí)變量，最后彻舰，在二層循環(huán)退出后伐割，如果臨時(shí)變量改變，則說明刃唤，有比當(dāng)前外層循環(huán)位置更小的元素隔心，需要將這兩個(gè)元素交換
public static void selectSort(int[]a)
{
int minIndex=0;
int temp=0;
if((a==null)||(a.length==0))
return;
for(int i=0;i<a.length-1;i++)
{
minIndex=i;//無序區(qū)的最小數(shù)據(jù)數(shù)組下標(biāo)
for(intj=i+1;j<a.length;j++)
{
//在無序區(qū)中找到最小數(shù)據(jù)并保存其數(shù)組下標(biāo)
if(a[j]<a[minIndex])
{
minIndex=j;
}
}
if(minIndex!=i)
{
//如果不是無序區(qū)的最小值位置不是默認(rèn)的第一個(gè)數(shù)據(jù)，則交換之尚胞。
temp=a[i];
a[i]=a[minIndex];
a[minIndex]=temp;
}
}
}
插入排序
插入排序：插入即表示將一個(gè)新的數(shù)據(jù)插入到一個(gè)有序數(shù)組中硬霍，并繼續(xù)保持有序。例如有一個(gè)長度為N的無序數(shù)組笼裳，進(jìn)行N-1次的插入即能完成排序唯卖；第一次，數(shù)組第1個(gè)數(shù)認(rèn)為是有序的數(shù)組躬柬，將數(shù)組第二個(gè)元素插入僅有1個(gè)有序的數(shù)組中拜轨；第二次，數(shù)組前兩個(gè)元素組成有序的數(shù)組允青，將數(shù)組第三個(gè)元素插入由兩個(gè)元素構(gòu)成的有序數(shù)組中......第N-1次橄碾，數(shù)組前N-1個(gè)元素組成有序的數(shù)組，將數(shù)組的第N個(gè)元素插入由N-1個(gè)元素構(gòu)成的有序數(shù)組中，則完成了整個(gè)插入排序堪嫂。
以下面5個(gè)無序的數(shù)據(jù)為例：
65 27 59 64 58 （文中僅細(xì)化了第四次插入過程）
第1次插入: 27 65 59 64 58
第2次插入: 27 59 65 64 58
第3次插入: 27 59 64 65 58
第4次插入: 27 58 59 64 65
void InsertSort(int* pDataArray, int iDataNum)
{
for (int i = 1; i < iDataNum; i++) //從第2個(gè)數(shù)據(jù)開始插入
{
int j = i - 1;
int temp = pDataArray[i]; //記錄要插入的數(shù)據(jù)
while (j >= 0 && pDataArray[j] > temp) //從后向前，找到比其小的數(shù)的位置
{
pDataArray[j+1] = pDataArray[j]; //向后挪動(dòng)
j--;
}
if (j != i - 1) //存在比其小的數(shù)
pDataArray[j+1] = temp;
}
}
