iT邦幫忙

第 11 屆 iThome 鐵人賽
DAY 14
0
自我挑戰組

練習程式系列 第 14 篇

java，quicksort、Counting Sort和c++ ，mergesort、Heap Sort和 js ，Shell Sort、Radix Sort

11th鐵人賽
2232 瀏覽

  • 分享至 

  • xImage
    •  

紀錄網路上大大的程式來源
以下程式都是複製貼上，只有增加print來看結果。

quicksort

教學來源:
2.8.1 QuickSort Algorithm
程式來源:
快速排序法(Quick Sort)
QuickSort

pivot 值 就是 以這個數 當 基準 . 左邊要比 pivot 值 小 ， 右邊要比 pivot 值 大

練習1:pivot取最前面arr[low]

class QuickSort {
 int partition(int arr[], int low, int high) {
  int pivot = arr[low];
  int i = low, j = high;
  while (i < j) {
   try {
    while (arr[i] <= pivot) i++;
   } catch (java.lang.ArrayIndexOutOfBoundsException e) {
    i = high;
   }
   while (arr[j] > pivot) j--;

   if (i < j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    System.out.print("交換:");
    printArray(arr);
   } else {
    break;
   }
  }

  int temp = arr[low];
  arr[low] = arr[j];
  arr[j] = temp;
  System.out.print("交換:找到pivot值(陣列索引):");
  System.out.print(j);
  System.out.print(",陣列:");
  printArray(arr);
  return j;
 }

 void sort(int arr[], int low, int high) {
  if (low < high) {
   int pi = partition(arr, low, high);
   sort(arr, low, pi-1);
   sort(arr, pi + 1, high);
  }
 }

 /*印陣列*/
 static void printArray(int arr[]) {
  int n = arr.length;
  for (int i = 0; i < n; ++i)
   System.out.print(arr[i] + " ");
  System.out.println();
 }

}

class Main {
 public static void main(String[] args) {
  int arr[] = {1,3,5,7,9,11,13,15,17}; 
  int n = arr.length;
  QuickSort ob = new QuickSort();
  ob.sort(arr, 0, n - 1);
  System.out.print("最後排序結果:");
  ob.printArray(arr);
  System.out.println();

  int arr1[] = {3,98,80,5,57,8,9}; 
  n = arr1.length;
  ob.sort(arr1, 0, n - 1);
  System.out.print("最後排序結果:");
  ob.printArray(arr1);
 }
}

交換:找到pivot值(陣列索引):0    ,陣列:  1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):1    ,陣列:  1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):2   ,陣列:  1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):3   ,陣列:  1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):4   ,陣列:  1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):5   ,陣列:  1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):6   ,陣列:  1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):7   ,陣列:  1 3 5 7 9 11 13 15 17
最後排序結果:  1 3 5 7 9 11 13 15 17
// worst 時間複雜度 就很明顯  是 n  * n
// 因為有 n個數,  每次檢查的數字 會是 n-1 ...n-2 ...n-3

  // int arr1[] = {3,98,80,5,57,8,9}; 
交換:找到pivot值(陣列索引):0,   陣列: 3 98 80 5 57 8 9
交換:找到pivot值(陣列索引):6,  陣列: 3 9 80 5 57 8 98
交換:3 9 8 5 57 80 98
交換:找到pivot值(陣列索引):3,  陣列: 3 5 8 9 57 80 98
交換:找到pivot值(陣列索引):1,  陣列: 3 5 8 9 57 80 98
交換:找到pivot值(陣列索引):2,  陣列: 3 5 8 9 57 80 98
交換:找到pivot值(陣列索引):4,  陣列: 3 5 8 9 57 80 98
交換:找到pivot值(陣列索引):5,  陣列: 3 5 8 9 57 80 98
最後排序結果:3 5 8 9 57 80 98

練習2，pivot取中間，arr[low + (high - low) / 2]
程式是錯的:

class QuickSort {
 int partition(int arr[], int low, int high) {
  int pivot = arr[low + (high - low) / 2];
  int i = low, j = high;
  while (i < j) {

   try {
    while (arr[i] <= pivot) i++;
   } catch (java.lang.ArrayIndexOutOfBoundsException e) {
    i = high;
   }
   while (arr[j] > pivot) j--;

   if (i < j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    System.out.print("交換:");
    printArray(arr);
   } else {
    break;
   }
  }

  int temp = arr[low + (high - low) / 2];
  arr[low + (high - low) / 2] = arr[j];
  arr[j] = temp;
  System.out.print("交換:找到pivot值(陣列索引):");
  System.out.print(j);
  System.out.print(",陣列:");
  printArray(arr);
  return j;
 }

 void sort(int arr[], int low, int high) {
  if (low < high) {
   int pi = partition(arr, low, high);
   sort(arr, low, pi);
   sort(arr, pi + 1, high);
  }
 }

 /*印陣列*/
 static void printArray(int arr[]) {
  int n = arr.length;
  for (int i = 0; i < n; ++i)
   System.out.print(arr[i] + " ");
  System.out.println();
 }

}

class Main {
 public static void main(String[] args) {
  int arr[] = {1,3,5,7,9,11,13,15,17}; 
  int n = arr.length;
  QuickSort ob = new QuickSort();
  ob.sort(arr, 0, n - 1);
  System.out.print("最後排序結果:");
  ob.printArray(arr);
  System.out.println();

  int arr1[] = {3,98,80,5,57,8,9}; 
  n = arr1.length;
  ob.sort(arr1, 0, n - 1);
  System.out.print("最後排序結果:");
  ob.printArray(arr1);
 }
}

交換:找到pivot值(陣列索引):4,  陣列:1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):2,  陣列:1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):1,  陣列:1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):0,  陣列:1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):3,  陣列:1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):6,  陣列:1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):5,  陣列:1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):7,  陣列:1 3 5 7 9 11 13 15 17
最後排序結果:1 3 5 7 9 11 13 15 17

//    猜測這個狀況 是 最好的時間複雜度  ？  因為 pivot值  每次sort後 都在中間   
//  

交換:3 5 80 98 57 8 9
交換:找到pivot值(陣列索引):1,陣列:3 98 80 5 57 8 9
交換:找到pivot值(陣列索引):0,陣列:3 98 80 5 57 8 9
交換:3 98 9 5 57 8 80
交換:找到pivot值(陣列索引):5,陣列:3 98 9 5 8 57 80
交換:3 98 5 9 8 57 80
交換:找到pivot值(陣列索引):2,陣列:3 98 9 5 8 57 80
交換:找到pivot值(陣列索引):4,陣列:3 98 9 5 8 57 80
交換:找到pivot值(陣列索引):3,陣列:3 98 9 5 8 57 80
最後排序結果:3 98 9 5 8 57 80

練習3，pivot取後面，arr[high]

class QuickSort {
 int partition(int arr[], int low, int high) {
  int pivot = arr[high];
  int i = low, j = high;
  while (i < j) {

   while (arr[i] < pivot) i++;
   try {
    while (arr[j] >= pivot) j--;
   } catch (java.lang.ArrayIndexOutOfBoundsException e) {
    j = low;
   }

   if (i < j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    System.out.print("交換:");
    printArray(arr);
   } else {
    break;
   }
  }

  int temp = arr[high];
  arr[high] = arr[i];
  arr[i] = temp;
  System.out.print("交換:找到pivot值(陣列索引):");
  System.out.print(i);
  System.out.print(",陣列:");
  printArray(arr);

  return i;
 }

 void sort(int arr[], int low, int high) {
  if (low < high) {
   int pi = partition(arr, low, high);
   sort(arr, low, pi-1);
   sort(arr, pi + 1, high);
  }
 }

 /*印陣列*/
 static void printArray(int arr[]) {
  int n = arr.length;
  for (int i = 0; i < n; ++i)
   System.out.print(arr[i] + " ");
  System.out.println();
 }

}


class Main {
 public static void main(String[] args) {
  int arr[] = {1,3,5,7,9,11,13,15,17}; 
  int n = arr.length;
  QuickSort ob = new QuickSort();
  ob.sort(arr, 0, n - 1);
  System.out.print("最後排序結果:");
  ob.printArray(arr);
  System.out.println();

  int arr1[] = {3,98,80,5,57,8,9}; 
  n = arr1.length;
  ob.sort(arr1, 0, n - 1);
  System.out.print("最後排序結果:");
  ob.printArray(arr1);
 }
}

交換:找到pivot值(陣列索引):8,陣列:1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):7,陣列:1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):6,陣列:1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):5,陣列:1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):4,陣列:1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):3,陣列:1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):2,陣列:1 3 5 7 9 11 13 15 17
交換:找到pivot值(陣列索引):1,陣列:1 3 5 7 9 11 13 15 17
最後排序結果:1 3 5 7 9 11 13 15 17

交換:3 8 80 5 57 98 9
交換:3 8 5 80 57 98 9
交換:找到pivot值(陣列索引):3,陣列:3 8 5 9 57 98 80
交換:找到pivot值(陣列索引):5,陣列:3 8 5 9 57 80 98
交換:找到pivot值(陣列索引):6,陣列:3 8 5 9 57 80 98
交換:找到pivot值(陣列索引):4,陣列:3 8 5 9 57 80 98
交換:找到pivot值(陣列索引):1,陣列:3 5 8 9 57 80 98
交換:找到pivot值(陣列索引):2,陣列:3 5 8 9 57 80 98
最後排序結果:3 5 8 9 57 80 98

問題:好像目前只有中間pivot的錯誤,其他的可以跑

後來有看這些：
Hoare’s vs Lomuto partition scheme in QuickSort
https://www.geeksforgeeks.org/hoares-vs-lomuto-partition-scheme-quicksort/?ref=rp

Quicksort
https://www.raywenderlich.com/books/data-structures-algorithms-in-swift/v3.0/chapters/34-quicksort

Quicksort大概有三種：
Lomuto’s partitioning ：挑陣列的最後一項當pivot, 把比pivot小的放到前半段

Hoare’s partitioning ：挑陣列的第一項當pivot,陣列左邊挑比pivot大的值,右邊挑比pivot小的值互換

Dutch national flag partitioning ：比pivot小的放左邊,相等的不動,大的放右邊.如果一個陣列只有三個數字,只要跑一次迴圈. pivot放哪應該都可以

mergesort

程式參考：
Comparison Sort: Merge Sort(合併排序法)
教學參考：
Merge Sort | GeeksforGeeks
2.7.2. Merge Sort Algorithm

照抄：

#include <iostream>
#include <vector>

const int Max = 1000;
class MergeMain {
  public: void Merge(std::vector < int > & Array, int front, int mid, int end) {

    std::vector < int > LeftSub(Array.begin() + front, Array.begin() + mid + 1),
                        RightSub(Array.begin() + mid + 1, Array.begin() + end + 1);

    LeftSub.insert(LeftSub.end(), Max);
    RightSub.insert(RightSub.end(), Max);

    int idxLeft = 0, idxRight = 0;

    for (int i = front; i <= end; i++) {

      if (LeftSub[idxLeft] <= RightSub[idxRight]) {
        Array[i] = LeftSub[idxLeft];
        idxLeft++;
      } else {
        Array[i] = RightSub[idxRight];
        idxRight++;
      }
    }
    std::cout << "process:\n";
    PrintArray(Array);
  }

  public: void MergeSort(std::vector < int > & array, int front, int end) {

    if (front < end) {
      int mid = (front + end) / 2;
      MergeSort(array, front, mid);
      MergeSort(array, mid + 1, end);
      Merge(array, front, mid, end);
    }
  }

  public: void PrintArray(std::vector < int > & array) {
    for (int i = 0; i < array.size(); i++) {
      std::cout << array[i] << " ";
    }
    std::cout << std::endl;
  }
};

int main() {
  MergeMain mergemain;
  int arr[] = {5,3,8,6,2,7,1,4};
  std::cout << " arr+sizeof(arr):" << arr + sizeof(arr) << "\n";
  std::cout << " sizeof(int):" << sizeof(int) << "\n";

  std::vector < int > array(arr, arr + sizeof(arr) / sizeof(int));

  std::cout << "original:\n";
  mergemain.PrintArray(array);

  mergemain.MergeSort(array, 0, 7);
  std::cout << "sorted:\n";
  mergemain.PrintArray(array);

  return 0;
}

結果：

 arr+sizeof(arr):0x7ffff7a8d940
 sizeof(int):4
original:
5 3 8 6 2 7 1 4
process:
3 5 8 6 2 7 1 4
process:
3 5 6 8 2 7 1 4
process:
3 5 6 8 2 7 1 4
process:
3 5 6 8 2 7 1 4
process:
3 5 6 8 2 7 1 4
process:
3 5 6 8 1 2 4 7
process:
1 2 3 4 5 6 7 8
sorted:
1 2 3 4 5 6 7 8

Heap Sort

程式來源:
Comparison Sort: Heap Sort(堆積排序法)
教學來源:
2.6.3 Heap - Heap Sort - Heapify - Priority Queues
Heap Sort | GeeksforGeeks

結果：

original:
9 4 1 6 7 3 8 2 5
original max heap :
0 9 7 8 6 4 3 1 2 5
process :
0 8 7 5 6 4 3 1 2 9
process :
0 7 6 5 2 4 3 1 8 9
process :
0 6 4 5 2 1 3 7 8 9
process :
0 5 4 3 2 1 6 7 8 9
process :
0 4 2 3 1 5 6 7 8 9
process :
0 3 2 1 4 5 6 7 8 9
process :
0 2 1 3 4 5 6 7 8 9
process :
0 1 2 3 4 5 6 7 8 9
sorted:
1 2 3 4 5 6 7 8 9

What is the difference between "ascending order" and "non-decreasing" order?

ascending order:遞增
ex:1 5 7
non-decreasing　order: 不會遞減
ex:1 5 5 7

Shell Sort

教學和程式來源:
[演算法] 希爾排序法(Shell Sort)
Shell Sort | GeeksforGeeks
Day11 -- Decrease and Conquer - Shell Sort
程式:
index.html

<!DOCTYPE html>
<html>
  <head>
    <title>shell sort</title>
  </head>
  <body>
    <script src="script.js"></script>
    <script>
      var numbers = [1,2,8,4,4,3,5,5];
      shellSort(numbers);
    </script>
  </body>
</html>

script.js

var swap = function(data, i, j){ 
    var tmp = data[i];
    data[i] = data[j];
    data[j] = tmp;
};
    
var shellSort = function(data){
    console.log("ori data:",data)
    var gap = parseInt(data.length/2);
    while(gap>0){
        for(var k = 0; k < gap; k++){
            for(var i = k + gap; i < data.length; i += gap){
                for(var j = i - gap; j >= k; j -= gap){
                    if(data[j] > data[j+gap])
                        swap( data, j, j+gap);
                    else
                        break;
                }
            }
        }
        gap = parseInt(gap/= 2);
    }
    console.log("res data:",data)
};

結果

ori data: [ 1, 2, 8, 4, 4, 3, 5, 5 ]
res data: [ 1, 2, 3, 4, 4, 5, 5, 8 ]

Radix Sort

教學和程式來源:
[演算法] 基數排序(Radix Sort)
Radix Sort Algorithm Introduction in 5 Minutes
Data Structures and Algorithms in Swift: Radix Sort

筆記:
1 swift的 array.flatMap可以把二維陣列變成一維陣列

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width">
    <title>Radix Sort</title>
    <link href="style.css" rel="stylesheet" type="text/css" />
  </head>
  <body>
    <script src="script.js"></script>
      <script>
      var numbers = [89,10,84,4];
      radixSort(numbers);
      </script>
  </body>
</html>

var initArray = function(buckets, count) {
 for (var i = 0; i < buckets.length; i++) {
  buckets[i] = new Array(buckets.length);
  count[i] = 0;
 }
}

var radixSort = function(data) {
 console.log("ori data:", data)
 var MAX = 100;
 var dataIndex = 0,
  radix = 1;
 var buckets = new Array(10), // 桶子 //可以放數字0 到 9
  count = new Array(data.length);
 initArray(buckets, count);

 while (radix <= MAX) {
  // 分配
  for (var i = 0; i < data.length; i++) {
   var LSD = parseInt((data[i] / radix)) % 10;
   buckets[LSD][ count[LSD] ]  = data[i]; //前面的LSD代表哪個桶子 ，後面的count[LSD]，代表桶子裡有幾個東西
   count[LSD]++;
  }

  radix *= 10;
  // 合併
  dataIndex = 0;
  for (var i = 0; i < 10; i++) {
   if (buckets[i][count[0]] != 0) {
    for (var j = 0; j < count[i]; j++) {
     data[dataIndex++] = buckets[i][j];
    }
   }
   count[i] = 0;
  }
  console.log("turn data:", data)
 }
 console.log("res data:", data)
};

結果:

ori data: [ 89, 10, 84, 4 ]
turn data: [ 10, 84, 4, 89 ]
turn data: [ 4, 10, 84, 89 ]
turn data: [ 4, 10, 84, 89 ]
res data: [ 4, 10, 84, 89 ]

Counting Sort

教學和程式來源:Learn Counting Sort Algorithm in LESS THAN 6 MINUTES!
計數排序法(Counting Sort)，只需線性時間就能完成的超快排序法
Day20 -- Time and Space Tradeoff- Distribution Sorting

class CountingSort {

 static void countingSortStable(final int[] array, final int min, final int max) {
  final int size = max - min + 1;

  final int[] count = new int[size]; //索引是數字 ，值是次數

  for (final int n: array) {
   count[n - min]++;
  }

  for (int i = 1; i < size; ++i) {
   count[i] += count[i - 1];
  }

  final int[] origin = array.clone(); //array.clone類似複製的功能 ，原本沒排序的陣列複製一份

  for (int i = array.length - 1; i >= 0; --i) {  //倒著走
   final int n = origin[i];
   array[--count[n - min]] = n;
  }
 }

 /*印陣列*/
 static void printArray(int arr[]) {
  int n = arr.length;
  for (int i = 0; i < n; ++i)
   System.out.print(arr[i] + " ");
  System.out.println();
 }


}
class Main {
 public static void main(String[] args) {
  int arr[] = {3,8,7,5,5,8,9}; 
  int n = arr.length;
  CountingSort.countingSortStable(arr, 0, 10);
  System.out.println("結果:");
  CountingSort.printArray(arr);
 }
}

結果:

結果:
3 5 5 7 8 8 9

上一篇
java，Bubble sort algorithm 和c++， Insertion Sort 、Selection Sort
下一篇
java ，Binary Search 和、計算時間、記憶體 和 c++ tree traversal 、 Binary Search Tree、infix、prefix、postfix
系列文
練習程式 共 37 篇
  1. 33
    Android ，存圖片到SQLite，process、thread、ByteArrayOutputStream
  2. 34
    Android 畫面、delete image、Apache（php） , 安裝apache,import library
  3. 35
    WEB 筆記
  4. 36
    Android，Navigation
  5. 37
    C# 筆記
完整目錄
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
1048 組
團體組數
40 組
累計文章數
14217 篇
最後報名日
9/15
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 16th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react 資訊安全
熱門問題
熱門回答
熱門文章
IT邦幫忙