国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

經(jīng)典排序算法及其 Java 實(shí)現(xiàn)

hiyang / 850人閱讀

摘要:冒泡排序插入排序選擇排序堆排序父節(jié)點(diǎn)索引尾節(jié)點(diǎn)索引歸并排序快速排序附錄交換方法基于策略模式的主程序?qū)崿F(xiàn)定義一個(gè)數(shù)組構(gòu)造函數(shù)初始化數(shù)組遍歷數(shù)組中每一個(gè)元素展示

</>復(fù)制代碼

  1. 「博客搬家」 原地址: 簡(jiǎn)書 原發(fā)表時(shí)間: 2017-08-17

網(wǎng)上有很多排序算法的總結(jié),不過有很多缺點(diǎn),比如有些根本就是錯(cuò)的,無法通過測(cè)試用例,有些過于冗長(zhǎng)。所以我總結(jié)了一套短小精悍的 Java 實(shí)現(xiàn),經(jīng)測(cè)試,該套實(shí)現(xiàn)可通過牛客網(wǎng)的關(guān)于此的所有測(cè)試用例。

1. 冒泡排序

</>復(fù)制代碼

  1. public class BubbleSort implements KySort {
  2. public void kySort(int[] a, int size) {
  3. for (int i = 0; i < size - 1; i++) {
  4. for (int j = 0; j < size - i - 1; j++) {
  5. if (a[j] > a[j + 1]) {
  6. swap(a, j, j + 1);
  7. }
  8. }
  9. }
  10. }
  11. }
2. 插入排序

</>復(fù)制代碼

  1. public class InsertSort implements KySort {
  2. public void kySort(int[] a, int size) {
  3. for (int i = 1; i < size; i++) {
  4. int temp = a[i];
  5. int j = i;
  6. while (j > 0 && a[j - 1] > temp) {
  7. a[j] = a[j - 1];
  8. j--;
  9. }
  10. a[j] = temp;
  11. }
  12. }
  13. }
3. 選擇排序

</>復(fù)制代碼

  1. public class SelectSort implements KySort {
  2. public void kySort(int[] a, int size) {
  3. for (int i = 0; i < size - 1; i++) {
  4. int min = i;
  5. for (int j = i + 1; j < size; j++) {
  6. if (a[j] < a[min]) {
  7. min = j;
  8. }
  9. }
  10. if (i != min) {
  11. swap(a, i, min);
  12. }
  13. }
  14. }
  15. }
4. 堆排序

</>復(fù)制代碼

  1. public class HeapSort implements KySort {
  2. public void kySort(int[] a, int n) {
  3. for (int i = n / 2; i >= 0; i--) {
  4. heapAdjust(a, i, n - 1);
  5. }
  6. for (int i = n - 1; i > 0; i--) {
  7. swap(a, 0, i);
  8. heapAdjust(a, 0, i - 1);
  9. }
  10. }
  11. /**
  12. * @param index 父節(jié)點(diǎn)索引
  13. * @param n 尾節(jié)點(diǎn)索引
  14. */
  15. private void heapAdjust(int[] a, int index, int n) {
  16. int temp = a[index];
  17. for (int child = index * 2 + 1; child <= n; child = index * 2 + 1) {
  18. if (child < n && a[child] < a[child + 1]) {
  19. child++;
  20. }
  21. if (temp > a[child]) break;
  22. a[index] = a[child];
  23. index = child;
  24. }
  25. a[index] = temp;
  26. }
  27. }
5. 歸并排序

</>復(fù)制代碼

  1. public class MergeSort implements KySort {
  2. public void kySort(int[] a, int size) {
  3. sort(a, 0, size - 1, new int[a.length]);
  4. }
  5. private void sort(int[] a, int left, int right, int[] temp) {
  6. if (left >= right) return;
  7. int mid = (left + right) / 2;
  8. sort(a, left, mid, temp);
  9. sort(a, mid + 1, right, temp);
  10. merge(a, left, mid, right, temp);
  11. }
  12. private void merge(int[] a, int left, int mid, int right, int[] temp) {
  13. int k = left;
  14. int i = left;
  15. int j = mid + 1;
  16. while (i <= mid && j <= right) {
  17. if (a[i] < a[j]) {
  18. temp[k++] = a[i++];
  19. } else {
  20. temp[k++] = a[j++];
  21. }
  22. }
  23. while (i <= mid) {
  24. temp[k++] = a[i++];
  25. }
  26. while (j <= right) {
  27. temp[k++] = a[j++];
  28. }
  29. while (left <= right) {
  30. a[left] = temp[left];
  31. left++;
  32. }
  33. }
  34. }
6. 快速排序

</>復(fù)制代碼

  1. public class QuickSort implements KySort {
  2. @Override
  3. public void kySort(int[] a, int size) {
  4. quickSort(a, 0, size - 1);
  5. }
  6. private void quickSort(int[] a, int left, int right) {
  7. if (right - left < 2) {
  8. if (a[left] > a[right])
  9. swap(a, left, right);
  10. return;
  11. }
  12. int p = middleBy3(a, left, right);
  13. quickSort(a, left, p - 1);
  14. quickSort(a, p + 1, right);
  15. }
  16. private int middleBy3(int[] a, int left, int right) {
  17. int p = (left + right) / 2;
  18. int end = right;
  19. if (a[left] > a[p]) swap(a, left, p);
  20. if (a[left] > a[right]) swap(a, left, right);
  21. if (a[p] > a[right]) swap(a, p, right);
  22. int temp = a[p];
  23. swap(a, p, right);
  24. while (true) {
  25. while (a[++left] < temp) ;
  26. while (a[--right] > temp) ;
  27. if (left >= right) break;
  28. else swap(a, left, right);
  29. }
  30. swap(a, left, end);
  31. return left;
  32. }
  33. }
7. 附錄 7.1 交換方法

</>復(fù)制代碼

  1. public class Util {
  2. public static void swap(int[] a, int i, int j) {
  3. int k = a[i];
  4. a[i] = a[j];
  5. a[j] = k;
  6. }
  7. }
7.2 基于策略模式的主程序?qū)崿F(xiàn)

</>復(fù)制代碼

  1. public class SortMain {
  2. private static KySort sorter;
  3. private int[] a;//定義一個(gè)數(shù)組
  4. private SortMain(int... values) { //構(gòu)造函數(shù)
  5. a = values;
  6. }
  7. public static void main(String[] args) {
  8. setSorter(new QuickSort());
  9. SortMain arr;
  10. arr = new SortMain(5, 4, 3, 2, 1, 0);
  11. arr.display();
  12. arr.kySort();
  13. arr.display();
  14. System.out.println("--------");
  15. arr = new SortMain(54, 35, 48, 36, 27, 12, 44, 44, 8, 14, 26, 17, 28);
  16. arr.display();
  17. arr.kySort();
  18. arr.display();
  19. System.out.println("--------");
  20. arr = new SortMain(32, 103, 24, 88, 95, 70, 97, 15, 102, 6, 79, 46, 51, 37, 93, 108, 9, 58, 53, 58, 79, 36, 58, 91, 78, 58, 61, 81); //初始化數(shù)組
  21. arr.display();
  22. arr.kySort();
  23. arr.display();
  24. }
  25. private static void setSorter(KySort sorter) {
  26. SortMain.sorter = sorter;
  27. }
  28. private void display() {
  29. for (int i : a) { //遍歷數(shù)組中每一個(gè)元素
  30. System.out.print(i + " "); //展示
  31. }
  32. System.out.println();
  33. }
  34. private void kySort() {
  35. sorter.kySort(a, a.length);
  36. }
  37. }

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/68246.html

相關(guān)文章

  • 十大經(jīng)典排序算法總結(jié)(Javascript描述)

    摘要:算法描述冒泡排序是一種簡(jiǎn)單的排序算法。算法描述和實(shí)現(xiàn)一般來說,插入排序都采用在數(shù)組上實(shí)現(xiàn)。平均情況希爾排序年發(fā)明第一個(gè)突破的排序算法是簡(jiǎn)單插入排序的改進(jìn)版它與插入排序的不同之處在于,它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。 前言 讀者自行嘗試可以想看源碼戳這,博主在github建了個(gè)庫(kù),讀者可以Clone下來本地嘗試。此博文配合源碼體驗(yàn)更棒哦~~~ 個(gè)人博客:Damonare的個(gè)人博客 原文地址:...

    Binguner 評(píng)論0 收藏0
  • 思維導(dǎo)圖整理大廠面試高頻數(shù)組24: 合并兩個(gè)有序數(shù)組的兩種雙指針?biāo)枷? 力扣88

    摘要:此專欄文章是對(duì)力扣上算法題目各種方法的總結(jié)和歸納整理出最重要的思路和知識(shí)重點(diǎn)并以思維導(dǎo)圖形式呈現(xiàn)當(dāng)然也會(huì)加上我對(duì)導(dǎo)圖的詳解目的是為了更方便快捷的記憶和回憶算法重點(diǎn)不用每次都重復(fù)看題解畢竟算法不是做了一遍就能完全記住的所 ...

    darkerXi 評(píng)論0 收藏0
  • 數(shù)據(jù)結(jié)構(gòu)與算法——常用排序算法及其Java實(shí)現(xiàn)

    摘要:數(shù)據(jù)結(jié)構(gòu)與算法常用數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)經(jīng)過前面文章的鋪墊,我們鞏固了基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的知識(shí),接下來就可以進(jìn)入算法的鞏固階段了。首先我們來看常見的排序算法。同樣的小規(guī)模數(shù)據(jù)轉(zhuǎn)換為插入排序會(huì)有效果提升。它只能對(duì)整數(shù)進(jìn)行排序。 數(shù)據(jù)結(jié)構(gòu)與算法——常用數(shù)據(jù)結(jié)構(gòu)及其Java實(shí)現(xiàn)經(jīng)過前面文章的鋪墊,我們鞏固了基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的知識(shí),接下來就可以進(jìn)入算法的鞏固階段了。首先我們來看常見的排序算法。 冒泡排序 原理...

    eternalshallow 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<