八大排序算法的java實(shí)現(xiàn)

有時(shí)間再貼算法分析圖

JDK7的Collections.sort()的算法是TimSort, 適應(yīng)性的歸并排序, 比較晦澀難懂, 這里沒有實(shí)現(xiàn)

public class mySort {// 冒泡排序public static void myBubbleSort(int[] array) {int lastExchange = array.length - 1; //記錄最后交換位置, 避免重復(fù)比較for (int i = lastExchange - 1; i >= 0; --i) {for (int j = 0; j <= i; ++j) {if (array[j] > array[j + 1]) {int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;lastExchange = j; //特性:最后交互位置后的元素已經(jīng)有序 }}}}// 插入排序public static void myInsertSort(int[] array) {for (int i = 1; i <= array.length - 1; ++i) {int temp = array[i];int j = 0; // 給值移位并尋找插入點(diǎn)for (j = i - 1; j >= 0 && array[j] > temp; --j) {array[j + 1] = array[j];}array[j + 1] = temp;}}// 選擇排序public static void mySelectSort(int[] array) {for (int i = 0; i < array.length - 1; ++i) {int minIndex = i;// 每次選出一極值for (int j = i + 1; j <= array.length - 1; ++j) {if (array[j] < array[minIndex]) {minIndex = j;}}// 極值歸位if (minIndex != i) {int temp = array[minIndex];array[minIndex] = array[i];array[i] = temp;}}}// 希爾排序public static void myShellSort(int[] array) {int gap = 5;while (gap != 0) {//不必刻意分組, 組1->組2->組1->組2...輪流處理for (int j = gap; j <= array.length - 1; ++j) {int temp = array[j];int k = 0;for (k = j - gap; k >= 0 && array[k] > temp; k -= gap) {array[k + gap] = array[k];}array[k + gap] = temp;}gap /= 2; //重新分組 }}// 快速排序public static void myQuickSort(int[] array) {myQuickSortCore(array, 0, array.length - 1);}private static void myQuickSortCore(int[] array, int left, int right) {if (left >= right) { //遞歸出口return;}int mLeft = left;int mRight = right;int base = array[mLeft]; //第一個(gè)元素作為基準(zhǔn), left空位可占while(mLeft != mRight) {while (mRight > mLeft && array[mRight] >= base) {--mRight;}array[mLeft] = array[mRight]; //right可覆蓋while (mRight > mLeft && array[mLeft] <= base) {++mLeft;}array[mRight] = array[mLeft];}array[mRight] = base; //基準(zhǔn)元素歸位, l=r myQuickSortCore(array, left, mLeft - 1); //遞歸基準(zhǔn)以左myQuickSortCore(array, mRight + 1 , right); //遞歸基準(zhǔn)以右 }// 歸并排序public static void myMergeSort(int[] array) {// 每個(gè)分組中有兩個(gè)來自上層迭代的有序組, gap為有序組長(zhǎng)度, 2 * gap為分組長(zhǎng)度for (int gap = 1; gap < array.length; gap *= 2) {int i = 0; // array下標(biāo)// 分組并內(nèi)部排序while (i + 2 * gap - 1 < array.length) {mergePiece(array, i, i + gap - 1, i + 2 * gap - 1);i += 2 * gap;}// 分組剩余部分排序, 只有超過一個(gè)gap才有內(nèi)部排序的意義if (i + gap - 1 < array.length) {mergePiece(array, i, i + gap - 1, array.length - 1);}}}// 將array中有序的兩段piecewise1 和 piecewise2 合并成整體有序public static void mergePiece(int[] array, int head, int mid, int tail) {int i = head; // piecewise1下標(biāo) [head, mid]int j = mid + 1; // piecewise2下標(biāo) [mid + 1, tail]// 臨時(shí)數(shù)組, 保存結(jié)果int[] arrayTemp = new int[tail - head + 1]; // combineint k = 0; // combine下標(biāo)while (i <= mid && j <= tail) {if (array[i] <= array[j]) {arrayTemp[k] = array[i];++i;++k;} else {arrayTemp[k] = array[j];++j;++k;}}// 復(fù)制多余部分 piecewise1while (i <= mid) {arrayTemp[k] = array[i];++i;++k;}// 復(fù)制多余部分 piecewise2while (j <= tail) {arrayTemp[k] = array[j];++j;++k;}// 結(jié)果復(fù)制到原始數(shù)組k = 0;i = head; // 重置下標(biāo), i piecewise1 + piecewise2while (i <= tail) {array[i] = arrayTemp[k];++i;++k;}}// 堆排序public static void myHeapSort(int[] array) {// 調(diào)整堆->大頂堆for (int i = array.length / 2 - 1; i >= 0; --i) { // 從最后非葉子節(jié)點(diǎn)開始 adjustHeap(array, i, array.length);}// 調(diào)整堆->交換堆頂/末位元素for (int j = array.length - 1; j > 0; --j) {int temp = array[0];array[0] = array[j];array[j] = temp;adjustHeap(array, 0, j); // 只需調(diào)整堆頂父節(jié)點(diǎn) }}// 調(diào)整為大頂堆分布, node為父節(jié)點(diǎn)下標(biāo), adjustLen為涉及調(diào)整的長(zhǎng)度(為排序使用)private static void adjustHeap(int[] array, int node, int adjustLen) {int temp = array[node]; // 拿出node形成可占空位for (int i = node * 2 + 1; i < adjustLen; i = node * 2 + 1) {if (i + 1 < adjustLen && array[i] < array[i + 1]) {++i; // 得到最大子節(jié)點(diǎn) }if (array[i] > temp) {array[node] = array[i];node = i; // 為下一層迭代更新父節(jié)點(diǎn)node, 最后為葉子} else {break;}}array[node] = temp;}// 基數(shù)排序public static void myRadixSort(int[] array) {int d = maxBit(array);int dec = 1; //進(jìn)制迭代final int R = 10; //桶個(gè)數(shù)int[] tempArray = new int[array.length]; //臨時(shí)數(shù)組, 代替桶存儲(chǔ)數(shù)組, 代價(jià)是需記錄下標(biāo)/數(shù)量來分割桶int[] bucketCapacity = new int[R]; //桶計(jì)數(shù) for (int i = 1; i <= d; ++i) {for (int j = 0; j < R; ++j) {bucketCapacity[j] = 0; //清空桶容量 }//計(jì)數(shù)1for (int j = 0; j < array.length; ++j) {int k = array[j] / dec % R; ++bucketCapacity[k];}//計(jì)數(shù)2 變累計(jì), 為分割for (int j = 1; j < R; ++j) {bucketCapacity[j] = bucketCapacity[j - 1] + bucketCapacity[j];}// 存儲(chǔ)進(jìn)桶for (int j = array.length - 1; j >= 0; --j) {int k = array[j] / dec % R; tempArray[bucketCapacity[k] - 1] = array[j];--bucketCapacity[k]; }// 寫出for(int j = 0; j < array.length; ++j) {array[j] = tempArray[j];}// 下一位dec *= 10;}}//求數(shù)組元素的最大位數(shù)private static int maxBit(int[] array) {int bit = 1;int dec = 10;for (int i = 0; i < array.length; ++i) {while (array[i] >= dec) {++bit;dec *= 10;}}return bit;} }

?

posted on 2017-04-09 16:57 myJavaEE 閱讀(...) 評(píng)論(...) 編輯 收藏

轉(zhuǎn)載于:https://www.cnblogs.com/myJavaEE/p/6685445.html

總結(jié)

以上是生活随笔為你收集整理的八大排序算法的java实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。