常見的基礎(chǔ)排序算法大體上可以分為9種,這篇先介紹比較簡(jiǎn)單的6種排序算法粘优。剩下的3種在下篇介紹。
冒泡排序
冒泡排序通過重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素学赛，如果他們的順序錯(cuò)誤就把他們交換過來，直到?jīng)]有再需要交換的元素為止（對(duì)n個(gè)項(xiàng)目需要O(n^2)的比較次數(shù)）吞杭。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端盏浇。
實(shí)現(xiàn)步驟
- 比較相鄰的元素。如果第一個(gè)比第二個(gè)大芽狗，就交換他們兩個(gè)绢掰。
- 對(duì)每一對(duì)相鄰元素做同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)童擎。這步做完后滴劲，最后的元素會(huì)是最大的數(shù)。
- 針對(duì)所有的元素重復(fù)以上的步驟顾复，除了最后一個(gè)班挖。
- 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較芯砸。
代碼
/**
* 冒泡排序
* 最差時(shí)間復(fù)雜度O(n^2)
* 最優(yōu)時(shí)間復(fù)雜度O(n)
* 平均時(shí)間復(fù)雜度O(n^2)
* 最差空間復(fù)雜度O(n) 輔助空間O(1)
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {1, 4, 2, 5, 6, 3};
//bubbleSort(arr);
advancedBubbleSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void bubbleSort(int[] arr) {
int len = arr.length;
int temp;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
/**
* 引入標(biāo)志位萧芙，默認(rèn)為true
* 如果前后數(shù)據(jù)進(jìn)行了交換，則為true假丧，否則為false双揪。如果沒有數(shù)據(jù)交換，則排序完成包帚。
*
* @param arr
*/
public static void advancedBubbleSort(int[] arr) {
boolean flag = true;
int n = arr.length;
while (flag) {
flag = false;
for (int j = 0; j < n - 1; j++) {
if (arr[j] > arr[j + 1]) {
//數(shù)據(jù)交換
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
//設(shè)置標(biāo)志位
flag = true;
}
}
n--;
}
}
}
插入排序
插入排序?qū)⒁粋€(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中渔期，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)渴邦，算法適用于少量數(shù)據(jù)的排序擎场，是穩(wěn)定的排序方法羽德。
實(shí)現(xiàn)步驟
直接插入排序
把待排序的紀(jì)錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的紀(jì)錄插入完為止迅办，得到一個(gè)新的有序序列宅静。
折半插入排序
折半插入排序,使用使用折半查找的方式尋找插入點(diǎn)的位置, 可以減少比較的次數(shù),但移動(dòng)的次數(shù)不變, 時(shí)間復(fù)雜度和空間復(fù)雜度和直接插入排序一樣，在元素較多的情況下能提高查找性能站欺。
代碼
private static void insertSort(int[] arr) {
int j;//當(dāng)前要插入值的位置
int preJ;//依次指向j前的位置
int key;//后移時(shí)來暫存要插入的值
//從數(shù)組的第二個(gè)位置開始遍歷值
for (j = 1; j < arr.length; j++) {
key = arr[j];
preJ = j - 1;
//arr[preJ]比當(dāng)前值大姨夹，arr[preJ]后移一位
while (preJ >= 0 && arr[preJ] > key) {
arr[preJ + 1] = arr[preJ]; //將a[preJ]值后移
//這里注意: a[preJ+1]=a[j]=key,把插入值已經(jīng)存在了 key中
//等于說, 留出來一個(gè)空白位置來實(shí)現(xiàn)依次后移（不會(huì)造成數(shù)據(jù)丟失問題）
preJ--;//preJ前移
}
//找到要插入的位置或已遍歷完成（(preJ=0）
arr[preJ + 1] = key;//將當(dāng)前值插入 空白位置
}
}
/**
*折半插入排序
*/
private static void binaryInsertSort(int[] arr){
//從數(shù)組的第二個(gè)位置開始遍歷值
for(int i = 1; i < arr.length; i++) {
int key = arr[i];//暫存要插入的值
int pre = 0;//有序序列開始和結(jié)尾下標(biāo)申明
int last = i - 1;
// 折半查找出插入位置 a[pre]
while(pre <= last) {
int mid = (pre + last) / 2;
if(key < arr[mid]) {
last = mid - 1;
} else {
pre = mid + 1;
}
}
//a[i]已經(jīng)取出來存放在key中，把下標(biāo)從pre + 1到 i-1的元素依次后移
for(int j = i; j >= pre + 1; j--) {
arr[j] = arr[j - 1];
}
//把值插入空白位置
arr[pre] = key;
}
}
歸并排序
歸并排序矾策，是創(chuàng)建在歸并操作上的一種有效的排序算法該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用磷账，且各層分治遞歸可以同時(shí)進(jìn)行。 歸并排序速度僅次于快速排序贾虽，為穩(wěn)定排序算法（即相等的元素的順序不會(huì)改變）逃糟，一般用于對(duì)總體無序，但是各子項(xiàng)相對(duì)有序的數(shù)列.
實(shí)現(xiàn)步驟
①申請(qǐng)空間蓬豁，使其大小為兩個(gè)已經(jīng)排序序列之和绰咽，該空間用來存放合并后的序列
②設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
③比較兩個(gè)指針?biāo)赶虻脑氐胤啵x擇相對(duì)小的元素放入到合并空間取募，并移動(dòng)指針到下一位置
④重復(fù)步驟③直到某一指針到達(dá)序列尾
⑤將另一序列剩下的所有元素直接復(fù)制到合并序列
代碼
private static void mergeSort(int[] arr) {
int len = arr.length;
//用于合并的臨時(shí)數(shù)組
int[] res = new int[len];
int block, start;
//倆倆合并后塊大小變大倆倍,(最后一次block等于len)
for (block = 1; block <= len; block *= 2) {
//把整個(gè)數(shù)組分成很多個(gè)塊，每次合并處理倆個(gè)塊
for (start = 0; start < len; start += block * 2) {
int low = start;
int mid = (start + block) < len ? (start + block) : len;
int high = (start + 2 * block) < len ? (start + 2 * block) : len;
//倆個(gè)塊的起始下標(biāo)和結(jié)束下標(biāo)
int start1 = start, end1 = mid;
int start2 = mid, end2 = high;
//開始對(duì)倆個(gè)block進(jìn)行歸并排序
while (start1 < end1 && start2 < end2) {
res[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
}
while (start1 < end1) {
res[low++] = arr[start1++];
}
while (start2 < end2) {
res[low++] = arr[start2++];
}
}
//每次歸并后把結(jié)果result存入arr中蟆技，以便進(jìn)行下次歸并
int[] temp = arr;
arr = res;
res = temp;
}
}
快速排序
基本思想
快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)玩敏，又稱劃分交換排序（partition-exchange sort。
快速排序使用分治法（Divide and conquer）策略來把一個(gè)序列（list）分為兩個(gè)子序列（sub-lists）质礼。實(shí)現(xiàn)原理
①．從數(shù)列中挑出一個(gè)元素旺聚，稱為"基準(zhǔn)"（pivot）
②．重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面眶蕉，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）翻屈。 在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置妻坝。這個(gè)稱為分區(qū)（partition）操作伸眶。
③．遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序
代碼
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int mid = getMiddle(arr, low, high);
quickSort(arr, low, mid - 1);
quickSort(arr, mid + 1, high);
}
}
private static int getMiddle(int[] arr, int low, int high) {
int temp = arr[low];
while (low < high) {
while (low < high && arr[high] >= temp) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= temp) {
low++;
}
arr[high] = arr[low];
}
arr[low] = temp;
return low;
}
簡(jiǎn)單選擇排序
在簡(jiǎn)單選擇排序過程中，所需移動(dòng)記錄的次數(shù)比較少刽宪。最好情況下厘贼，即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了，則不需要移動(dòng)記錄圣拄∽旖眨
最壞情況下，即待排序記錄初始狀態(tài)是按第一條記錄最大，之后的記錄從小到大順序排列岳掐，則需要移動(dòng)記錄的次數(shù)最多為3（n-1）凭疮。
簡(jiǎn)單選擇排序過程中需要進(jìn)行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況無關(guān)
不穩(wěn)定的排序
代碼
public static void simpleSort(int[] arr){
int len = arr.length;
int temp;
for (int i=0;i<len-1;i++){
int min = i;
for (int j=i+1;j<len;j++){//尋找最小的數(shù)
if(arr[j]<arr[min]){
min = j;
}
}
if(min!=i){
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}
希爾排序
希爾排序是一個(gè)不穩(wěn)定的排序，其時(shí)間復(fù)雜度受步長(zhǎng)（增量）的影響串述。
代碼
private static void shellSort(int[] arr) {
int gap = 1, i, j, len = arr.length;
int temp;
while (gap < len / 3) {//確定初始步長(zhǎng)
gap = gap * 3 + 1;
}
for (; gap > 0; gap /= 3) {//循環(huán)遍歷步長(zhǎng)执解，最后必為1
for (i = gap; i < len; i++) {//每一列依次向前做插入排序
temp = arr[i];
//每一列中在arr[i]上面且比arr[i]大的元素依次向下移動(dòng)
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j + gap] = arr[j];
;
}
//arr[i]填補(bǔ)空白,完成一列中的依次插入排序
arr[j + gap] = temp;
}
}
}
