閱讀本文約需要7分鐘

大家好，我是你們的導師，我每天都會在這里給大家分享一些干貨內容(當然了，周末也要允許老師休息一下哈)。上次老師跟大家分享了下用Navicat for Mysql導入.sql文件的相關知識，今天跟大家分享在 各種排序算法的分析及java實現(一)的知識。參考來源：https://www.cnblogs.com/liuling/p/2013-7-24-01.html

新的一周又開始了，這周也要打起精神好好加油！今天我們開始了解排序。

排序大的分類可以分為兩種：內排序和外排序。在排序過程中，全部記錄存放在內存，則稱為內排序，如果排序過程中需要使用外存，則稱為外排序。下面講的排序都是屬于內排序。

內排序有可以分為以下幾類：

　　(1)、插入排序：直接插入排序、二分法插入排序、希爾排序。

　　(2)、選擇排序：簡單選擇排序、堆排序。

　　(3)、交換排序：冒泡排序、快速排序。

　　(4)、歸并排序

　　(5)、基數排序?

一、插入排序

?思想：每步將一個待排序的記錄，按其順序碼大小插入到前面已經排序的字序列的合適位置，直到全部插入排序完為止。

?關鍵問題：在前面已經排好序的序列中找到合適的插入位置。

?方法：

–直接插入排序

–二分插入排序

–希爾排序

①直接插入排序(從后向前找到合適位置后插入)

1、基本思想

每步將一個待排序的記錄，按其順序碼大小插入到前面已經排序的字序列的合適位置(從后向前找到合適位置后)，直到全部插入排序完為止。

2、實例

　　

　3、java實現

package com.sort; public class 直接插入排序 { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1}; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } //直接插入排序 for (int i = 1; i < a.length; i++) { //待插入元素 int temp = a[i]; int j; /*for (j = i-1; j>=0 && a[j]>temp; j--) { //將大于temp的往后移動一位 a[j+1] = a[j]; }*/ for (j = i-1; j>=0; j--) { //將大于temp的往后移動一位 if(a[j]>temp){ a[j+1] = a[j]; }else{ break; } } a[j+1] = temp; } System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } }

4、分析

直接插入排序是穩定的排序。關于各種算法的穩定性分析可以參考

http://www.cnblogs.com/Braveliu/archive/2013/01/15/2861201.html文件初態不同時，直接插入排序所耗費的時間有很大差異。若文件初態為正序，則每個待插入的記錄只需要比較一次就能夠找到合適的位置插入，故算法的時間復雜度為O(n)，這時最好的情況。若初態為反序，則第i個待插入記錄需要比較i+1次才能找到合適位置插入，故時間復雜度為O(n2)，這時最壞的情況。直接插入排序的平均時間復雜度為O(n2)。

②二分法插入排序(按二分法找到合適位置插入)

　　1、基本思想

二分法插入排序的思想和直接插入一樣，只是找合適的插入位置的方式不同，這里是按二分法找到合適的位置，可以減少比較的次數。

　　2、實例

　　3、java實現

package com.sort; public class 二分插入排序 { public static void main(String[] args) { int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1}; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } //二分插入排序 sort(a); System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } private static void sort(int[] a) { for (int i = 0; i < a.length; i++) { int temp = a[i]; int left = 0; int right = i-1; int mid = 0; while(left<=right){ mid = (left+right)/2; if(temp right = mid-1; }else{ left = mid+1; } } for (int j = i-1; j >= left; j--) { a[j+1] = a[j]; } if(left != i){ a[left] = temp; } } } }

　　4、分析

　當然，二分法插入排序也是穩定的。二分插入排序的比較次數與待排序記錄的初始狀態無關，僅依賴于記錄的個數。當n較大時，比直接插入排序的最大比較次數少得多。但大于直接插入排序的最小比較次數。算法的移動次數與直接插入排序算法的相同，最壞的情況為n2/2，最好的情況為n，平均移動次數為O(n2)。

③希爾排序

　1、基本思想：

先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序。

然后，取第二個增量d2

　　2、實例

　3、java實現

package com.sort; //不穩定 public class 希爾排序 { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1}; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } //希爾排序 int d = a.length; while(true){ d = d / 2; for(int x=0;x for(int i=x+d;i int temp = a[i]; int j; for(j=i-d;j>=0&&a[j]>temp;j=j-d){ a[j+d] = a[j]; } a[j+d] = temp; } } if(d == 1){ break; } } System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } }

　　4、分析

我們知道一次插入排序是穩定的，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩定性就會被打亂，所以希爾排序是不穩定的。希爾排序的時間性能優于直接插入排序，原因如下：

(1)當文件初態基本有序時直接插入排序所需的比較和移動次數均較少。(2)當n值較小時，n和n2的差別也較小，即直接插入排序的最好時間復雜度O(n)和最壞時間復雜度0(n2)差別不大。(3)在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，后來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由于已經按di-1作為距離排過序，使文件較接近于有序狀態，所以新的一趟排序過程也較快。因此，希爾排序在效率上較直接插人排序有較大的改進。希爾排序的平均時間復雜度為O(nlogn)。

二、選擇排序

?思想：每趟從待排序的記錄序列中選擇關鍵字最小的記錄放置到已排序表的最前位置，直到全部排完。

?關鍵問題：在剩余的待排序記錄序列中找到最小關鍵碼記錄。

?方法：

–直接選擇排序

–堆排序

①簡單的選擇排序

　　1、基本思想

在要排序的一組數中，選出最小的一個數與第一個位置的數交換；然后在剩下的數當中再找最小的與第二個位置的數交換，如此循環到倒數第二個數和最后一個數比較為止。

　　2、實例

　　3、java實現

package com.sort; //不穩定 public class 簡單的選擇排序 { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } //簡單的選擇排序 for (int i = 0; i < a.length; i++) { int min = a[i]; int n=i; //最小數的索引 for(int j=i+1;j if(a[j] min = a[j]; n = j; } } a[n] = a[i]; a[i] = min; } System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } }

?? 　4、分析

　　簡單選擇排序是不穩定的排序。

　時間復雜度：T(n)=O(n2)。

②堆排序

　1、基本思想：

堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。

堆的定義下：具有n個元素的序列 (h1,h2,...,hn),當且僅當滿足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1) (i=1,2,...,n/2)時稱之為堆。在這里只討論滿足前者條件的堆。

由堆的定義可以看出，堆頂元素(即第一個元素)必為最大項(大頂堆)。完全二 叉樹可以很直觀地表示堆的結構。堆頂為根，其它為左子樹、右子樹。

思想:初始時把要排序的數的序列看作是一棵順序存儲的二叉樹，調整它們的存儲序，使之成為一個 堆，這時堆的根節點的數最大。然后將根節點與堆的最后一個節點交換。然后對前面(n-1)個數重新調整使之成為堆。

依此類推，直到只有兩個節點的堆，并對 它們作交換，最后得到有n個節點的有序序列。從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最后一個元素交換位置。所以堆排序有兩個函數組成。一是建堆的滲透函數，二是反復調用滲透函數實現排序的函數。

　　2、實例

初始序列：46,79,56,38,40,84建堆：

?　　交換，從堆中踢出最大數

依次類推：最后堆中剩余的最后兩個結點交換，踢出一個，排序完成。

　　3、java實現

package com.sort; //不穩定 import java.util.Arrays; public class HeapSort { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64}; int arrayLength=a.length; //循環建堆 for(int i=0;i //建堆 buildMaxHeap(a,arrayLength-1-i); //交換堆頂和最后一個元素 swap(a,0,arrayLength-1-i); System.out.println(Arrays.toString(a)); } } //對data數組從0到lastIndex建大頂堆 public static void buildMaxHeap(int[] data, int lastIndex){ //從lastIndex處節點(最后一個節點)的父節點開始 for(int i=(lastIndex-1)/2;i>=0;i--){ //k保存正在判斷的節點 int k=i; //如果當前k節點的子節點存在 while(k*2+1<=lastIndex){ //k節點的左子節點的索引 int biggerIndex=2*k+1; //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k節點的右子節點存在 if(biggerIndex //若果右子節點的值較大 if(data[biggerIndex] //biggerIndex總是記錄較大子節點的索引 biggerIndex++; } } //如果k節點的值小于其較大的子節點的值 if(data[k] //交換他們 swap(data,k,biggerIndex); //將biggerIndex賦予k，開始while循環的下一次循環，重新保證k節點的值大于其左右子節點的值 k=biggerIndex; }else{ break; } } } } //交換 private static void swap(int[] data, int i, int j) { int tmp=data[i]; data[i]=data[j]; data[j]=tmp; } }

　　4、分析

堆排序也是一種不穩定的排序算法。

堆排序優于簡單選擇排序的原因：

直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然后在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。

事實上，后面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經做過，但由于前一趟排序時未保留這些比較結果，所以后一趟排序時又重復執行了這些比較操作。

堆排序可通過樹形結構保存部分比較結果，可減少比較次數。

堆排序的最壞時間復雜度為O(nlogn)。堆序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數較多，所以堆排序不適宜于記錄數較少的文件。

今天就分享這么多，關于各種排序算法的分析及java實現(一)，你學會了多少？歡迎在留言區評論，對于有價值的留言，我們都會一一回復的。如果覺得文章對你有一丟丟幫助，請點右下角【在看】，讓更多人看到該文章。如果有想了解的，也可以進行留言

總結

以上是生活随笔為你收集整理的java实现apriori算法_各种排序算法的分析及java实现（一）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。