nlogn比n^2快多?

?

?O(nlogn)算法一: 歸并排序(Merge Sort)

// 歸并排序 public class MergeSort {private static void MergeSort(int[] arr, int n){_MergeSort(arr, 0, n-1);}private static void _MergeSort(int[] arr, int l, int r){if(l>=r)return;int mid = (l+r)/2;_MergeSort(arr, l, mid);_MergeSort(arr, mid+1, r);_Merge(arr, l, mid, r);}private static void _Merge(int[] arr, int l, int mid, int r) {// 經(jīng)測試,傳遞aux數(shù)組的性能效果并不好// l 4, mid 4, r 5int aux[] = new int[r - l + 1];for (int i = l; i <= r; i++)aux[i - l] = arr[i];int i = l, j = mid + 1;for (int k = l; k <= r; k++) {if (i > mid) {arr[k] = aux[j - l];j++;} else if (j > r) {arr[k] = aux[i - l];i++;} else if (aux[i - l] < aux[j - l]) {arr[k] = aux[i - l];i++;} else {arr[k] = aux[j - l];j++;}}}public static void main(String[] args){System.out.println("merge sort");int n = 50000;int arr[] = SortTestHelper.generateRandomArray(n, 0, n);long startTime = System.currentTimeMillis();MergeSort(arr,n);long endTime = System.currentTimeMillis();System.out.println(endTime-startTime);//SortTestHelper.printArray(arr, n);boolean sorted = SortTestHelper.isSorted(arr, n);System.out.println(sorted);} }// 輔助類 import java.util.Random;public class SortTestHelper {// 隨機(jī)生成數(shù)組// 生成有n個(gè)元素的隨機(jī)數(shù)組,每個(gè)元素的隨機(jī)范圍為[rangeL, rangeR]public static int[] generateRandomArray(int n, int rangeL, int rangeR){int[] arr = new int[n];for(int i=0;i<n;i++){arr[i] = new Random().nextInt(rangeR-rangeL)+rangeL;}return arr;}// 打印數(shù)組static void printArray(int arr[], int n) {for(int i=0; i<n; i++){System.out.println(arr[i]+" ");}}public static boolean isSorted(int arr[], int n){for(int i=0; i<n-1; i++){if(arr[i] > arr[i+1])return false;}return true;} }

?

快速排序(Quicksort)

??

public class QuickSort {public static int partition(int[] arr, int l, int r){int e = arr[l];int j = l; // for(int i=l+1; i<=r; i++){ // if(arr[i]<e){ // int temp = arr[i]; // for(int j=i;j>t;j--){ // arr[j] = arr[j-1]; // } // arr[t] = temp; // t++; // } // }for(int i=l+1; i<=r; i++){if(arr[i] < e){int temp = arr[j+1];arr[j+1] = arr[i];arr[i] = temp;j++;}}int temp = arr[j];arr[j] = arr[l];arr[l] = temp;return j;}public static void quickSort(int[] arr, int l, int r){if(l >= r)return;int p = partition(arr, l, r);quickSort(arr, l, p-1);quickSort(arr, p+1, r);}public static void quickSort(int[] arr, int n){quickSort(arr, 0, n-1);}public static void main(String[] args){System.out.println("QuickSort sort");int n = 50000;int arr[] = SortTestHelper.generateRandomArray(n, 0, n);//int arr[] = SortTestHelper.generateRandomArrayNearOrder(n, 10);long startTime = System.currentTimeMillis();quickSort(arr,n);long endTime = System.currentTimeMillis();System.out.println(endTime-startTime);//SortTestHelper.printArray(arr, n);boolean sorted = SortTestHelper.isSorted(arr, n);System.out.println(sorted);} }// 輔助類 import java.util.Random;public class SortTestHelper {// 隨機(jī)生成數(shù)組// 生成有n個(gè)元素的隨機(jī)數(shù)組,每個(gè)元素的隨機(jī)范圍為[rangeL, rangeR]public static int[] generateRandomArray(int n, int rangeL, int rangeR){int[] arr = new int[n];for(int i=0;i<n;i++){arr[i] = new Random().nextInt(rangeR-rangeL)+rangeL;}return arr;}// 近乎有序的數(shù)組序列public static int[] generateRandomArrayNearOrder(int n, int swapTimes){int[] arr = new int[n];for(int i=0;i<n;i++){arr[i] = i;}for( int i = 0 ; i < swapTimes ; i ++ ){int posx = new Random().nextInt(n);int posy = new Random().nextInt(n);int temp = arr[posx];arr[posx] = arr[posy];arr[posy] = temp;}return arr;}// 打印數(shù)組static void printArray(int arr[], int n) {for(int i=0; i<n; i++){System.out.println(arr[i]+" ");}}public static boolean isSorted(int arr[], int n){for(int i=0; i<n-1; i++){if(arr[i] > arr[i+1])return false;}return true;} }

?

總結(jié)

以上是生活随笔為你收集整理的数据结构:O(nlogn)算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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