java排序代碼，java內置排序有哪些_內部排序比較（Java版）

內部排序比較(Java版)

2017-06-21

目錄

java排序代碼。1 三種基本排序算法

1.1 插入排序

public static void InsertSort(int[] arrs) {intj;inttmp;for (int i = 1; i < arrs.length; i++) {

tmp=arrs[i];for (j = i - 1; j >= 0 && tmp < arrs[j]; j--) {

arrs[j+ 1] =arrs[j];

}

JAVA排序算法。arrs[j+ 1] =tmp;

}

}

1.2 交換排序(冒泡)

public static void BubbleSortS(int[] arrs) {inttmp;for (int i = arrs.length - 1; i > 0; i--) {for (int j = 0; j < i; j++) {if (arrs[j] > arrs[j + 1]) {

tmp=arrs[j];

java排序方法有哪幾種，arrs[j]= arrs[j + 1];

arrs[j+ 1] =tmp;

}

}

}

}

java數組從小到大排序。1.3 選擇排序(簡單)

public static void SelectSort(int[] arrs) {intminIndex;inttmp;for (int i = 0; i < arrs.length - 1; i++) {

minIndex=i;for (int j = i + 1; j < arrs.length; j++) {if (arrs[minIndex] >arrs[j])

minIndex=j;

}if (minIndex !=i) {

tmp=arrs[minIndex];

選擇排序java？arrs[minIndex]=arrs[i];

arrs[i]=tmp;

}

}

}

2 比較

快速排序java？排序方法

復雜度

輔助空間

內外循環

一次內循環取最大數

一次循環交換次數

如何使用java排序、插入排序

O(n2)

1

i=1->length-1

j=i-1->0

否

java list排序？O(1)

冒泡排序

O(n2)

1

i=length-1->1

j=0->i-1

是

O(n)

選擇排序

O(n2)

2

i=0->length-1

j=i+1->length-1

是

O(1)

內部排序(C#)

3 補充

3.1 快速排序

快速排序是對冒泡排序的一種改進。

時間復雜度，最壞是O(n2)，一般O(nlogn)，

空間復雜度(遞歸實現)，在一般情況下的空間復雜度為O(logn)，在最差的情況下，若每次只完成了一個元素，那么空間復雜度為O(n)

/*** 快速排序是在冒泡排序的基礎上改進而來的，冒泡排序每次只能交換相鄰的兩個元素，而快速排序是跳躍式的交換，交換的距離很大，因此總的比較和交換次數少了很多，速度也快了不少。

* 時間復雜度，最壞是O(n2)，一般O(nlogn)*/

public classQuickSort

{public static voidmain(String[] args)

{int[] arr=new int[]{1,5,2,3,6,8,4,9,7,5};

QuickSort quickSort=newQuickSort(arr);

quickSort.sort();

quickSort.print();

}private int[] arr;public QuickSort(int[] arr)

{this.arr=arr;

}public voidsort()

{

quickSort(arr,0,arr.length-1);

}public void quickSort(int[] arr,int begin,intend)

{if(begin

{int i =partition(arr, begin, end);

quickSort(arr,begin,i-1);

quickSort(arr,i+1,end);

}

}private int partition(int[] arr, int begin, intend) {int key=arr[begin];while(begin

{while (begin=key)end--;if(begin

arr[begin]=arr[end];

}while(begin

arr[end]=arr[begin];

}

}

arr[begin]=key;returnbegin;

}public voidprint()

{for(intvalue:arr)

System.out.println(value);

}

}

View Code

3.2 什么是桶排序

桶排序，也叫作箱排序，是一個排序算法，也是所有排序算法中最快、最簡單的排序算法。其中的思想是我們首先需要知道所有待排序元素的范圍，然后需要有在這個范圍內的同樣數量的桶，接著把元素放到對應的桶中，最后按順序輸出。

時間復雜度為O(n+m)

空間復雜度是O(m)，其中m為桶的個數，

/*** 桶排序，也叫作箱排序，是一個排序算法，也是所有排序算法中最快、最簡單的排序算法。

* 其中的思想是我們首先需要知道所有待排序元素的范圍，然后需要有在這個范圍內的同樣數量的桶，接著把元素放到對應的桶中，最后按順序輸出。

* 由于時間復雜度為O(n+m)，m為桶容量,如果m比n大太多，則從時間上來說，性能也并不是很好。*/

public classBucketSort {public static voidmain(String[] args)

{int[] needSortedArr=new int[]{9,2,3,0,3};

BucketSort bucketSort=new BucketSort(10,needSortedArr);

bucketSort.sort();

bucketSort.print();

}private int[] buckets;private int[] array;public BucketSort(int range,int[] array)

{this.buckets=new int[range];this.array=array;

}public voidsort()

{if(array!=null&&array.length!=0)

{for(int i=0;i

{

buckets[array[i]]++;

}

}

}public voidprint()

{for(int i=0;i

{for(int j=buckets[i];j>0;j--)

System.out.println(i);

}

}

}

View Code

3.3 堆排序

堆的定義

我們可以吧這個序列看成一個二叉樹，可得，?1)最大堆的根節點最大，2)上層總比下層大

時間復雜度是O(logn)

public classHeapSort {public static voidmain(String[] args) {int[] array = { 8, 6, 9, 7, 5, 4, -3, -2, -1, 0, 1, 2, 3};

System.out.println("Before heap:");

printArray(array);

printHeapTree(array);

System.out.println("build max heap:");

buildMaxHeap(array);

printArray(array);

printHeapTree(array);

heapSort(array);

System.out.println("After heap sort:");

printArray(array);

printHeapTree(array);

}public static void heapSort(int[] array) {if (array == null || array.length <= 1) {return;

}//建大頂堆

buildMaxHeap(array);//堆排序

for (int i = array.length - 1; i >= 1; i--) {

exchangeElements(array,0, i);

maxHeap(array, i,0);

}

}private static void buildMaxHeap(int[] array) {if (array == null || array.length <= 1) {return;

}int half = array.length / 2-1;for (int i = half; i >= 0; i--) {

maxHeap(array, array.length, i);

}

}//時間復雜度O(logN)

private static void maxHeap(int[] array, int heapSize, intindex) {int left = index * 2 + 1;int right = index * 2 + 2;int largest =index;if (left < heapSize && array[left] >array[index]) {

largest=left;

}if (right < heapSize && array[right] >array[largest]) {

largest=right;

}if (index !=largest) {

exchangeElements(array, index, largest);

maxHeap(array, heapSize, largest);

}

}public static void printArray(int[] array) {

System.out.print("{");for (int i = 0; i < array.length; i++) {

System.out.print(array[i]);if (i < array.length - 1) {

System.out.print(", ");

}

}

System.out.println("}");

}private static void printHeapTree(int[] array)

{for(int i=1;i

{for(int k=i-1;k<2*(i)-1&&k

{

System.out.print(array[k]+" ");

}

System.out.println();

}

}public static void exchangeElements(int[] array, int index1, intindex2) {int temp =array[index1];

array[index1]=array[index2];

array[index2]=temp;

}

}

View Code