八大排序算法（java版）
點擊上方藍(lán)色字體，選擇“標(biāo)星公眾號”
優(yōu)質(zhì)文章，第一時間送達(dá)
冒泡排序
public?static?void?popSort(int[] array)?{
???????for?(int?i = 0; i < array.length; i++) {
???????????for?(int?j = 0; j < array.length-i-1; j++) {//每次遍歷都會使一個最大的數(shù)歸位
???????????????if?(array[j] > array[j + 1]) {
???????????????????swap(array, j, j + 1);
???????????????}
???????????}
???????}
???}
???/**
????* 交換數(shù)組array中下標(biāo)為j、i的元素
????* @param array
????* @param j
????* @param i
????*/
???private?static?void?swap(int[] array, int?j, int?i)?{
???????int?tmp = array[j];
???????array[j] = array[i];
???????array[i] = tmp;
???}冒泡排序核心思想就是每次將兩個相鄰元素對比，并且把較大的元素放在后面。如此一來每次遍歷都會使一個最大的元素到達(dá)其排序完成后的位置，比如第一次遍歷時就會將最大的一個元素放到最后一個位置。那么只要遍歷N（數(shù)組元素數(shù)量）遍就會使得所有元素均到達(dá)其應(yīng)該在的位置。在第二層循環(huán)是這樣寫的for (int j = 0; j < array.length-i-1; j++)之所以要使array.length-i也就是這個原因，之后的元素已經(jīng)是排好序的了，所以并不需要繼續(xù)遍歷下去，當(dāng)然即使不減去i也可以正常完成排序。因為遍歷它們也不會對結(jié)果造成影響。時間復(fù)雜度就是O(n)*O(n)=O(n^2)。從上面的代碼也可以看出冒泡排序是穩(wěn)定的，相同元素在排序過程中并不會改變相對位置。無論是對有序還是無序的數(shù)組，遍歷次數(shù)都是一樣的，只是有序數(shù)組不會進(jìn)行交換操作，對時間復(fù)雜度無影響。
插入排序
public?static?void?insertSort(int[] array)?{
????????for?(int?i = 1; i < array.length; i++) {
????????????int?tmp = array[i];
????????????int?j = i;
????????????while?(j > 0?&& array[j - 1] > tmp) {//將大于tmp的數(shù)往后移
????????????????array[j] = array[j - 1];
????????????????j--;
????????????}
????????????array[j] = tmp;//插入
????????}
????}插入排序也叫直接插入排序，核心思想是假設(shè)在第i個數(shù)字之前的數(shù)組元素是有序的。那么只需要從第i個元素向前遍歷將比第i個數(shù)字大的元素往后移，碰到比i小的元素就插入進(jìn)去即可。
希爾排序
希爾排序就是直接插入排序的改進(jìn)版，也屬于一種插入排序。改進(jìn)的地方在與，每次遍歷設(shè)置一個步長然后進(jìn)行直接插入排序，完成一次遍歷就將步長減半，直到步長小于等于1。由于每次移動都會移動一個步長的距離，而直接插入排序每次移動只移動一步，所以希爾排序的效率是要比直接插入排序的效率要高的。
public?static?void?shellSort(int[] array)?{
????????int?step = array.length;
????????while?(true) {
????????????step /= 2;
????????????for?(int?i = 0; i < step; i++) {
????????????????for?(int?j = i + step; j < array.length; j += step) {
????????????????????int?tmp = array[j];
????????????????????int?k = j;
????????????????????while?(k >=step && array[k - step] > tmp) {//將大于tmp的數(shù)往后移
????????????????????????array[k] = array[k - step];
????????????????????????k-=step;
????????????????????}
????????????????????array[k] = tmp;//插入
????????????????}
????????????}
????????????if?(step <= 1)
????????????????return;
????????}
????}快速排序
public?static?void?fastSort(int[] array)?{
????????if?(array?== null)
????????????throw?new?NullPointerException();
????????fastSortHelp(array, 0, array.length - 1);
????}
??private?static?void?fastSortHelp(int[] array, int?left, int?right)?{
????????if?(right > left) {
????????????int?index = getIndex(array, left, right);
????????????fastSortHelp(array, left, index - 1);
????????????fastSortHelp(array, index + 1, right);
????????}
????}
????private?static?int?getIndex(int[] array, int?left, int?right)?{
????????int?tmp = array[left];
????????while?(left < right) {
????????????while?(left < right && array[right] > tmp) {//找到第一個比tmp小的數(shù)
????????????????right--;
????????????}
????????????if?(left < right) {
????????????????array[left] = array[right];
????????????????left++;
????????????}
????????????while?(left < right && array[left] < tmp) {
????????????????left++;
????????????}
????????????if?(left < right) {
????????????????array[right] = array[left];
????????????????right--;
????????????}
????????}
????????array[left] = tmp;
????????return?left;
????}快速排序是一個常用的排序算法，當(dāng)數(shù)組順序越混亂它的效率越高。用來求數(shù)組的第k大的元素也非常好用。getIndex(int[] array, int left, int right)這一個方法是核心，它將所有大于array[left]的元素放在右邊，小于它的放在左邊，那么就得到了array[left]排序完成后的坐標(biāo)，然后對它的左右子數(shù)組分別遞歸調(diào)用快速排序，即可完成排序。也正是由于這個方法的特性，每次調(diào)用getIndex()方法就會使得一個元素回到它應(yīng)該在的位置。所以這個方法返回的下標(biāo)k就是第k大或者第k小的元素。
歸并排序
歸并排序是一個非原地排序算法，他需要用額外O(n)的空間來儲存排序完成后的數(shù)組，然后返回這一個排好序的數(shù)組，對原數(shù)組并不會改動。這一特性可用于一些不希望改變原數(shù)組的情況，且免于對原數(shù)組進(jìn)行拷貝。核心思想就是’分而治之’，每次將數(shù)組分為左右兩半，然后對這兩個子數(shù)組繼續(xù)遞歸調(diào)用，直到不能分割，然后在回溯過程中將左右數(shù)組合并。合并過程就是排序過程，申請一個足夠容納左右子數(shù)組所有元素的新數(shù)組，然后每次取出左右數(shù)組中較小/較大的元素，放入新的數(shù)組，以此保證新數(shù)組有序。然后將這個新的數(shù)組返回，完成排序。
public?static?int[] mergeSort(int[] array) {
????????if?(array?== null)
????????????throw?new?NullPointerException();
????????array?= mergeSortHelp(array, 0, array.length - 1);
????????return?array;
????}
????private?static?int[] mergeSortHelp(int[] array, int?start, int?end) {
????????if?(start == end)
????????????return?new?int[]{array[start]};
????????else?{
????????????int?mid = (end + start) / 2;
????????????int[] leftArray = mergeSortHelp(array, start, mid);
????????????int[] rightArray = mergeSortHelp(array, mid + 1, end);
????????????return?mergeArray(leftArray, rightArray);
????????}
????}
????private?static?int[] mergeArray(int[] leftArray, int[] rightArray) {
????????int[] newArray = new?int[leftArray.length + rightArray.length];
????????int?nIndex = 0, lIndex = 0, rIndex = 0;
????????while?(lIndex < leftArray.length && rIndex < rightArray.length) {//每次取出一個較大的數(shù)復(fù)制到新數(shù)組
????????????newArray[nIndex++] = leftArray[lIndex] > rightArray[rIndex] ? rightArray[rIndex++] : leftArray[lIndex++];
????????}
????????while?(lIndex < leftArray.length) {
????????????newArray[nIndex++] = leftArray[lIndex++];
????????}
????????while?(rIndex < rightArray.length)
????????????newArray[nIndex++] = rightArray[rIndex++];
????????return?newArray;
????}選擇排序
public?static?void?selectSort(int[] array)?{
????????//每次選擇最小元素，放在第一個位置
????????for?(int?i = 0; i < array.length; i++) {
????????????int?minIndex = i;
????????????for?(int?j = i + 1; j < array.length; j++) {//獲得最小元素下標(biāo)
????????????????if?(array[j] < array[minIndex])
????????????????????minIndex = j;
????????????}
????????????swap(array,i,minIndex);
????????}
????}也叫簡單選擇排序，這名字也確實符合它的特點。這個算法很簡單，第i次遍歷從數(shù)組后length-i個元素里找到最小的元素，然后將它放在第i個。就相當(dāng)于與有兩個數(shù)組，每次從沒有排序的數(shù)組里移除一個最小的元素，放到排好序的數(shù)組里，直到?jīng)]有排序的數(shù)組元素都被移除。
堆排序
堆排序也是一種選擇排序，同樣是每次遍歷拿出一個最大/最小的數(shù)字放到數(shù)組尾部（這么說并不準(zhǔn)確，應(yīng)該說是放到已排序數(shù)組的頭部，只不過我們在原地排序，這個已排序數(shù)組我們將其放在原始數(shù)組的尾部，所以叫它尾部）然后繼續(xù)對數(shù)組進(jìn)行同樣的操作，直到所有數(shù)字均被取出。與簡單選擇排序不同的是，我們維護(hù)一個堆，每次堆頂元素都是未排序數(shù)組的最大值。這樣取出最大元素的操作就不必每次遍歷所有未排序元素了。
public?static?void?heapSort(int[] array)?{
????????//把數(shù)組當(dāng)成滿二叉樹
????????//i結(jié)點的左孩子下標(biāo)為i*2+1.
????????for?(int?i = array.length / 2?- 1; i >= 0; i--) {//構(gòu)建大頂堆
????????????siftDown(array, i, array.length);
????????}
????????for?(int?i = array.length - 1; i >= 0; i--) {//將堆頂元素放置最后（堆大小-1），然后重新構(gòu)建大頂堆
????????????swap(array, 0, i);
????????????siftDown(array, 0, i);
????????}
????}
????private?static?void?siftDown(int[] array, int?i, int?length)?{
????????int?key = array[i];
????????int?half = length >>> 1;
????????while?(i < half) {
????????????int?child = (i << 1) + 1;
????????????if?(child + 1?< length && array[child] < array[child + 1]) {
????????????????child++;
????????????}
????????????if?(array[child] <= key) {
????????????????break;
????????????}
????????????array[i] = array[child];
????????????i = child;
????????}
????????array[i] = key;
????}siftDown(int[] array, int i, int length)是一個下沉操作，它將第i個元素下沉。那么何種情況會下沉呢？當(dāng)子節(jié)點比它大時就下沉，將較大的元素上浮。這樣可以保證對于堆中的任意一個節(jié)點，它的所有子孫節(jié)點都比它小。Java中的PriorityQueue就是采用的這種方式維護(hù)大頂堆/小頂堆。下面是PriorityQueue中的一段源碼:
private?static? void?siftDownComparable(int?k, T x, Object[] es, int?n)?{
????????// assert n > 0;
????????Comparablesuper?T> key = (Comparablesuper?T>)x;
????????int?half = n >>> 1; // loop while a non-leaf
????????while?(k < half) {
????????????int?child = (k << 1) + 1; // assume left child is least
????????????Object c = es[child];
????????????int?right = child + 1;
????????????if?(right < n &&
????????????????((Comparablesuper?T>) c).compareTo((T) es[right]) > 0)
????????????????c = es[child = right];
????????????if?(key.compareTo((T) c) <= 0)
????????????????break;
????????????es[k] = c;
????????????k = child;
????????}
????????es[k] = key;
????} 基數(shù)排序/桶排序
…那個本人也還沒有掌握這種算法，手撕不出來。且容我學(xué)習(xí)一會再更…
版權(quán)聲明：本文為博主原創(chuàng)文章，遵循?CC 4.0 BY-SA?版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接和本聲明。
本文鏈接：
https://blog.csdn.net/First_C0de/article/details/107958580
粉絲福利：108本java從入門到大神精選電子書領(lǐng)取
???
?長按上方鋒哥微信二維碼?2 秒 備注「1234」即可獲取資料以及 可以進(jìn)入java1234官方微信群
感謝點贊支持下哈?