1、冒泡排序
- 算法思想
鄰位交換
若想升序排序流强，則將大的數(shù)值往后面冒慎玖，第一輪排序?qū)⒆畲蟮慕粨Q到數(shù)組最后一位贮尖，第二輪將次大的交換到數(shù)組倒數(shù)第二位，依次類推趁怔。
- 代碼實(shí)現(xiàn)
public class BubbleSort
{
public static int[] bubbleSort(int[] array)
{
for(int i = 0; i < array.length - 1; i++)
{
for(int j = 0; j < array.length - 1 - i; j++)
{
//冒泡排序：通過(guò)前后交換的方式將最大的移到最后
if(array[j] > array[j + 1])
{
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
return array;
}
public static void main(String[] args)
{
int[] array = new int[]{22,44,77,33,99,66};
int[] result = bubbleSort(array);
for(int i = 0; i<result.length;i++)
{
System.out.println(result[i]);
}
}
}
- 復(fù)雜度
時(shí)間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(1) - 穩(wěn)定性
相鄰元素相等時(shí)不會(huì)交換湿硝，穩(wěn)定性好。 - 使用場(chǎng)景
數(shù)據(jù)量小的情況润努；基本有序的情況 - 算法改進(jìn)
設(shè)置標(biāo)識(shí)位关斜，若當(dāng)前一輪沒(méi)有發(fā)生任何交換，說(shuō)明該數(shù)組已有序铺浇，直接退出痢畜，不再執(zhí)行下一輪比較。加上標(biāo)識(shí)位后鳍侣，可以將最好時(shí)間復(fù)雜度降為O(n)丁稀，初始即為正序情況。
2倚聚、快速排序
- 算法思想
分割 + 遞歸
1线衫、選擇一個(gè)基準(zhǔn)，一般為中間位或者左側(cè)位秉沼；
2桶雀、左右兩側(cè)往中間走矿酵，左邊遇到比基準(zhǔn)大的，右邊遇到比基準(zhǔn)小的矗积，兩者交換全肮；
3、以基準(zhǔn)值為界棘捣，將數(shù)組分為兩部分辜腺，分別重復(fù)步驟1-2
public class QuickSort
{
public static void quickSort(int[] arr, int low, int high)
{
if(low >= high)
{
return;
}
int i = low;
int j = high;
int pivot = arr[(low + high)/2];
while(i <= j)
{
while(arr[i] < pivot)
{
i++;
}
while(arr[j] > pivot)
{
j--;
}
if(i < j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
else if(i == j)
{
i++;
}
}
quickSort(arr,low,j);
quickSort(arr,i,high);
}
public static void main(String[] args)
{
int[] array = new int[]{22,44,77,88,189,22,22,35,666,33,99,66};
quickSort(array, 0, array.length - 1);
for(int i = 0; i<array.length;i++)
{
System.out.println(array[i]);
}
}
}
- 復(fù)雜度
時(shí)間復(fù)雜度：O(nlogn)
每一次分割后均需遍歷所有元素，使用時(shí)間O(n)乍恐。最好的情況评疗，每次的分割成幾乎大小一致的兩部分，到達(dá)大小為一的數(shù)列前茵烈，只要做logn次嵌套的調(diào)用百匆，調(diào)用樹的深度是O(logn)；最壞的情況呜投，每次分割1和n-1加匈，退化成冒泡排序時(shí)間復(fù)雜度變?yōu)镺(n^2)。
空間復(fù)雜度：最壞O(n)仑荐，最好O(logn)
- 穩(wěn)定性
不穩(wěn)定 - 使用場(chǎng)景
數(shù)據(jù)量大雕拼、初始排序隨機(jī)；基于比較的排序中性能最好粘招。
