亚洲日日夜,亚洲第一视频在线播放,男同志与动人物zo

概述

在計(jì)算器科學(xué)與數(shù)學(xué)中，一個(gè)排序算法（英語(yǔ)：Sorting algorithm）是一種能將一串?dāng)?shù)據(jù)依照特定排序方式進(jìn)行排列的一種算法。本文將總結(jié)幾類(lèi)常用的排序算法，包括冒泡排序、選擇排序、插入排序、快速排序和歸并排序，分別使用Java代碼實(shí)現(xiàn)，簡(jiǎn)要使用圖例方式介紹其實(shí)現(xiàn)原理。

算法原理及實(shí)現(xiàn)

1、冒泡排序

原理圖

理解

通過(guò)重復(fù)地遍歷要排序的列表，比較每對(duì)相鄰的項(xiàng)目，并在順序錯(cuò)誤的情況下交換它們。

Java Code

public class BubbleSort { // logic to sort the elements public static void bubble_srt(int array[]) { int n = array.length; int k; for (int m = n; m >= 0; m--) { for (int i = 0; i < n - 1; i++) { k = i + 1; if (array[i] > array[k]) { swapNumbers(i, k, array); } } printNumbers(array); } } private static void swapNumbers(int i, int j, int[] array) { int temp; temp = array[i]; array[i] = array[j]; array[j] = temp; } private static void printNumbers(int[] input) { for (int i = 0; i < input.length; i++) { System.out.print(input[i] + ', '); } System.out.println('\n'); } public static void main(String[] args) { int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 }; bubble_srt(input); }}

2、選擇排序

原理圖

理解

內(nèi)部循環(huán)查找下一個(gè)最?。ɑ蜃畲螅┲?，外部循環(huán)將該值放入其適當(dāng)?shù)奈恢谩?/p>

Java Code

public class SelectionSort {  public static int[] doSelectionSort(int[] arr){  for (int i = 0; i < arr.length - 1; i++) { int index = i; for (int j = i + 1; j < arr.length; j++) if (arr[j] < arr[index])  index = j;  int smallerNumber = arr[index];  arr[index] = arr[i]; arr[i] = smallerNumber; } return arr; }  public static void main(String a[]){  int[] arr1 = {10,34,2,56,7,67,88,42}; int[] arr2 = doSelectionSort(arr1); for(int i:arr2){ System.out.print(i); System.out.print(', '); } }}

冒泡排序和選擇排序的區(qū)別

1、冒泡排序是比較相鄰位置的兩個(gè)數(shù)，而選擇排序是按順序比較，找最大值或者最小值；2、冒泡排序每一輪比較后，位置不對(duì)都需要換位置，選擇排序每一輪比較都只需要換一次位置；3、冒泡排序是通過(guò)數(shù)去找位置，選擇排序是給定位置去找數(shù)。

3、插入排序

原理圖

理解

每一步將一個(gè)待排序的記錄，插入到前面已經(jīng)排好序的有序序列中去，直到插完所有元素為止。

Java Code

public class InsertionSort {  public static void main(String a[]){ int[] arr1 = {10,34,2,56,7,67,88,42}; int[] arr2 = doInsertionSort(arr1); for(int i:arr2){ System.out.print(i); System.out.print(', '); } }  public static int[] doInsertionSort(int[] input){  int temp; for (int i = 1; i < input.length; i++) { for(int j = i ; j > 0 ; j--){ if(input[j] < input[j-1]){ temp = input[j]; input[j] = input[j-1]; input[j-1] = temp; } } } return input; }}

4、快速排序

原理圖

理解

將原問(wèn)題分解為若干個(gè)規(guī)模更小，但結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題，遞歸地解這些子問(wèn)題，然后將這些子問(wèn)題的解組合為原問(wèn)題的解。

Java Code

public class QuickSort { private int array[]; private int length; public void sort(int[] inputArr) { if (inputArr == null || inputArr.length == 0) { return; } this.array = inputArr; length = inputArr.length; quickSort(0, length - 1); } private void quickSort(int lowerIndex, int higherIndex) { int i = lowerIndex; int j = higherIndex; // calculate pivot number, I am taking pivot as middle index number int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2]; // Divide into two arrays while (i <= j) { /** * In each iteration, we will identify a number from left side which * is greater then the pivot value, and also we will identify a number * from right side which is less then the pivot value. Once the search * is done, then we exchange both numbers. */ while (array[i] < pivot) { i++; } while (array[j] > pivot) { j--; } if (i <= j) { exchangeNumbers(i, j); //move index to next position on both sides i++; j--; } } // call quickSort() method recursively if (lowerIndex < j) quickSort(lowerIndex, j); if (i < higherIndex) quickSort(i, higherIndex); } private void exchangeNumbers(int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void main(String a[]){ MyQuickSort sorter = new MyQuickSort(); int[] input = {24,2,45,20,56,75,2,56,99,53,12}; sorter.sort(input); for(int i:input){ System.out.print(i); System.out.print(' '); } }}

5、歸并排序

原理圖

理解

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

Java Code

public class MergeSort {  private int[] array; private int[] tempMergArr; private int length;  public static void main(String a[]){  int[] inputArr = {45,23,11,89,77,98,4,28,65,43}; MyMergeSort mms = new MyMergeSort(); mms.sort(inputArr); for(int i:inputArr){ System.out.print(i); System.out.print(' '); } }  public void sort(int inputArr[]) { this.array = inputArr; this.length = inputArr.length; this.tempMergArr = new int[length]; doMergeSort(0, length - 1); }  private void doMergeSort(int lowerIndex, int higherIndex) {  if (lowerIndex < higherIndex) { int middle = lowerIndex + (higherIndex - lowerIndex) / 2; // Below step sorts the left side of the array doMergeSort(lowerIndex, middle); // Below step sorts the right side of the array doMergeSort(middle + 1, higherIndex); // Now merge both sides mergeParts(lowerIndex, middle, higherIndex); } }  private void mergeParts(int lowerIndex, int middle, int higherIndex) {  for (int i = lowerIndex; i <= higherIndex; i++) { tempMergArr[i] = array[i]; } int i = lowerIndex; int j = middle + 1; int k = lowerIndex; while (i <= middle && j <= higherIndex) { if (tempMergArr[i] <= tempMergArr[j]) { array[k] = tempMergArr[i]; i++; } else { array[k] = tempMergArr[j]; j++; } k++; } while (i <= middle) { array[k] = tempMergArr[i]; k++; i++; } }}

常見(jiàn)排序算法復(fù)雜度

作者：taro_秋刀魚(yú)

本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊舉報(bào)。

免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版