java教程簡書，排序算法java 簡書_手撕算法---常見排序算法java實現

冒泡排序

是一種比較并交換排序方式。兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止。

private void sort(int[] arr){

for (int i = 0; i < arr.length; i++) {

for (int j = i+1; j < arr.length; j++) {

java教程簡書？if (arr[i] > arr[j]){

swap(arr,i,j );

}

}

}

}

java 排序算法、protected void swap(int[] arr,int i,int j){

int tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

}

private void sort2(int[] arr){

java算法題？for (int i = 0; i < arr.length; i++) {

for (int j = arr.length - 2; j >= i ; j--) {

if (arr[j] > arr[j+1]){

swap(arr,j,j+1);

}

}

java常用算法、}

}

選擇排序

每一趟從待排序的記錄中選出最小的元素，順序放在已排好序的序列起始位置，直到全部記錄排序完畢。

public void sort(int[] arr) {

for (int i = 0; i < arr.length; i++) {

java數據結構和算法，int index = i;

for (int j = i+1; j < arr.length; j++) {

if (arr[index] > arr[j]){

index = j;

}

}

java遞歸，swap(arr,index,i);

}

}

直接插入排序

將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據。

public void sort(int[] arr) {

java排序。for (int i = 1; i < arr.length; i++) {

if (arr[i] < arr[i -1]){

int tmp = arr[i];

int j;

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

arr[j+1] = arr[j];

java。}

arr[j+1] = tmp;

}

}

}

希爾排序

java從入門到精通好嗎，又稱為縮小增量排序。把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。

public void sort(int[] arr) {

//增量插入排序

int increment = arr.length;

do {

increment = increment / 3 + 1;

java從入門到精通 mobi。for (int i = increment; i < arr.length; i+=increment) {

if (arr[i] < arr[i - increment]){

int tmp = arr[i];

int j;

for (j = i - increment; j >= 0 && arr[j] > tmp; j-=increment) {

arr[j + increment] = arr[j];

實現快速排序算法java，}

arr[j+increment] = tmp;

}

}

}while (increment > 1);

}

java從入門到精通pdf。堆排序

將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。將其與末尾元素進行交換，此時末尾就為最大值。然后將剩余n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反復執行，便得到一個有序序列。

public void sort(int[] arr) {

int n = (arr.length - 1)/2;

for (int i = n; i >= 0 ; i--) {

maxHeap(arr,i,arr.length - 1);

java學習，}

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

swap(arr,0,i);

maxHeap(arr,0,i);

}

}

java常用的排序算法。private void maxHeap(int[] arr, int i, int count) {

int j = 2 * i + 1;

int tmp = arr[i];

while (j < count){

if (j + 1 < count && arr[j] < arr[j + 1]){

j++;

}

if (arr[j] <= tmp){

break;

}

arr[i] = arr[j];

i = j;

j = 2 * i + 1;

}

arr[i] = tmp;

}

歸并排序

將待排序的數列分成若干個長度為1的子數列，然后將這些數列兩兩合并；得到若干個長度為2的有序數列，再將這些數列兩兩合并；得到若干個長度為4的有序數列，再將它們兩兩合并；直接合并成一個數列為止。

public void sort(int[] arr) {

int[] tmp = new int[arr.length];

mergeSort(arr,tmp,0,arr.length - 1);

}

private void mergeSort(int[] arr,int[] tmp, int start, int end) {

if (start < end){

int middle = (start + end)/2;

mergeSort(arr,tmp,start,middle);

mergeSort(arr,tmp,middle + 1,end);

merge(arr,tmp,start,middle,end);

}

}

private void merge(int[] arr,int[] tmp,int start, int middle, int end) {

int m = middle + 1;

int s = start;

int k = 0;

while (start <= middle && m <= end){

if (arr[start] < arr[m]){

tmp[k++] = arr[start++];

}else {

tmp[k++] = arr[m++];

}

}

while (start <= middle){

tmp[k++] = arr[start++];

}

while (m <= end){

tmp[k++] = arr[m++];

}

for (int i = 0; i < k; i++) {

arr[s + i] = tmp[i];

}

}

快速排序

選擇一個基準數，通過一趟排序將要排序的數據分割成獨立的兩部分；其中一部分的所有數據都比另外一部分的所有數據都要小。然后，再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

public void sort(int[] arr) {

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

}

private void quickSort(int[] arr, int start, int end) {

if (start < end){

int index = quickSortPartition(arr,start,end);

quickSort(arr,start,index);

quickSort(arr,index + 1,end);

}

}

private int quickSortPartition(int[] arr, int start, int end) {

int sentry = arr[start];

while (start < end){

//從右邊開始

while (start < end && arr[end] >= sentry){

end--;

}

if (start < end){

arr[start] = arr[end];

start++;

}

while (start < end && arr[start] <= sentry){

start++;

}

if (start < end){

arr[end] = arr[start];

end--;

}

}

arr[start] = sentry;

return start;

}

算法復雜度

算法的復雜度