排序演算法
排序演算法算是我們學習演算法的入門篇，在正式介紹各種排序演算法前，先介紹一下要用到的一些術語：
- 穩定排序：如果a本來在b的前面，且a==b，排序以后a依舊在b的前面，那就是穩定排序，否在是非穩定排序
- 原地排序：就是在排序程序中不申請多于的存盤空間，只利用原來存盤待排資料的存盤空間進行比較和交換的資料排序，而非原地排序就是需要利用額外的陣列來輔助排序，
總覽：
選擇排序
代碼思路
首先找到陣列中最小的元素，其次將其與陣列中第一個元素交換位置，然后在剩下的陣列中找到最小的元素，然后和第二個元素交換，以此類推，直到交換完畢，
特點
資料移動最少，運行時間與資料輸入時的順序無關
復雜度與排序特點
- 時間復雜度：O(n2)
- 空間復雜度：O(1)
- 非穩定排序
- 原地排序
使用環境
資料量少
演算法代碼
// 從小到大
private static void sort(int[] nums){
int n=nums.length;
int minIndex,temp;
for(int i=0;i<n-1;i++){
minIndex=i;
for(int j=i+1;j<n;j++){
if(nums[j]<nums[minIndex]){
minIndex=j;
}
}
temp=nums[i];
nums[i]=nums[minIndex];
nums[minIndex]=temp;
}
}
插入排序
代碼思路
像抓牌一樣，將牌暫時放入現在的適當的位置，當到最后一個元素時就排序完成了，就像把一個無序陣列中的資料整合到一個有序陣列中，
特點
運行時間與輸入情況有關，對于一個部分有序（陣列中元素離最終位置都不遠，或者一個有序的大陣列加一個小陣列）來說速度比較快
復雜度
- 時間復雜度：O(n2)
- 空間復雜度：O(1)
- 穩定排序
- 原地排序
使用環境
陣列基本有序，或者一個有序的大陣列中添加一些小資料，
演算法代碼
// 從小到大排序
private static void sort(int[] nums) {
int n=nums.length;
int preIndex,current;
for(int i=1;i<n;i++){
preIndex=i-1;
current=nums[i];
while (preIndex>=0&&nums[preIndex]>current){
nums[preIndex+1]=nums[preIndex];
preIndex--;
}
nums[preIndex+1]=current;
}
}
冒泡排序
代碼思路
十分簡單，重復訪問，依次比較進行交換，交換過多
- 比較相鄰元素，大就交換
- 從第一對開始，到最后一對，一次排序后保證最大的位于末尾
- 重復n次
特點
思路簡單
復雜度
- 時間復雜度：O(n2)
- 空間復雜度：O(1)
- 穩定排序
- 原地排序
使用環境
無適用場景一般用于學習演算法，
演算法代碼
private static void sort(int[] nums) {
int n=nums.length;
for(int i=0;i<n-1;i++){
for(int j=0;j<n-i-1;j++){
if(nums[j]>nums[j+1]){
int temp=nums[j];
nums[j]=nums[j+1];
nums[j+1]=temp;
}
}
}
}
改良冒泡排序演算法
在我們遍歷的程序中，會發現從開始第一隊到最后一對都沒有發生交換，此時意味著，剩下這些待排序的元素已經是有序的資料，無序再次排序，所以我們可以引入一個標志，當遇到此情況的時候，直接跳出回圈，減少無意義的比較和縮短排序時間，
希爾排序（縮小增量排序）
代碼思路
希爾排序是插入排序的一種變種，原來插入排序的優勢在于資料基本有序的情況下性能很好，但是如果原陣列中的元素距離其正確位置很遠的話，效率就不是很高，而希爾排序正是優化了這一點，
希爾排序就是為了加快速度簡單的改進了插入排序，交換不相鄰的元素以對資料的區域進行排序，
先使陣列中任意間隔為h的元素是有序的，最后對于一個以1結尾的的h序列我們都能夠將其排序，
具體步驟：
-
先將整個待排序的記錄序列分隔成若干子序列，分別進行直接插入排序
-
- 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列個數k，對序列進行k 趟排序；
- 每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序，僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度，
特點
基于插入排序的快速排序
復雜度
- 時間復雜度：O(nlogn)
- 空間復雜度：O(1)
- 非穩定排序
- 原地排序
使用環境
大型陣列，大多數情況下希爾排序都是比較高效且簡單的演算法
演算法代碼
private static void sort(int[] nums) {
int n=nums.length;
int gap=n/2;
while (gap>0){
for(int j=gap;j<n;j++){
int i=j;
while ((i>=gap&&nums[i-gap]>nums[i])){
int temp=nums[i];
nums[i]=nums[i-gap];
nums[i-gap]=temp;
i-=gap;
}
}
gap=gap/2;
}
}
需要注意的是，對各個分組進行插入的時候并不是先對一個組排序完了再對另一個組排序，而是輪流對每個組進行排序，
歸并排序
代碼思路
將一個大的無序陣列有序，我們可以利用歸并的思想來進行排序，即將大問題化為小問題進行解決，
- 把長度為n的輸入序列分成兩個長度為n/2的子序列；
- 對這兩個子序列分別采用歸并排序；
- 將兩個排序好的子序列合并成一個最終的排序序列，
特點
速度較快，不受輸入資料的影響，所需額外空間與N成正比
復雜度
- 時間復雜度：O(nlogn)
- 空間復雜度：O(n)
- 穩定排序
- 非原地排序
使用環境
演算法代碼
private static void sort(int[] nums,int start,int end) {
// 如果left==right，表明陣列中只有一個元素，則不用遞回排序
if(start<end){
// 將大陣列分割成兩個小陣列
int mid=(start+end)/2;
// 分別排序
sort(nums,start,mid);
sort(nums,mid+1,end);
// 進行合并
merge(nums,start,mid,end);
}
}
// 合并函式，把兩個有序的陣列合并起來
private static void merge(int[] nums,int left,int mid,int right){
int []tmp=new int[nums.length];
int p1=left,p2=mid+1,k=0;
while (p1<=mid && p2<=right){
if(nums[p1]<=nums[p2])
tmp[k++]=nums[p1++];
else
tmp[k++]=nums[p2++];
}
while (p1<=mid)
tmp[k++]=nums[p1++];
while (p2<=right)
tmp[k++]=nums[p2++];
// 把陣列復制到原陣列中
for (int i=left;i<=right;i++)
nums[i]=tmp[i];
}
快排（三取樣切分）
代碼思路
我們從陣列中選擇一個元素，我們把這個元素稱之為中軸元素吧，然后把陣列中所有小于中軸元素的元素放在其左邊，所有大于或等于中軸元素的元素放在其右邊，顯然，此時中軸元素所處的位置的是有序的，也就是說，我們無需再移動中軸元素的位置，
從中軸元素那里開始把大的陣列切割成兩個小的陣列(兩個陣列都不包含中軸元素)，接著我們通過遞回的方式，讓中軸元素左邊的陣列和右邊的陣列也重復同樣的操作，直到陣列的大小為1，此時每個元素都處于有序的位置，
特點
應用廣泛，原地排序，幾乎不需要額外的空間
復雜度
- 時間復雜度：O(nlogn)
- 空間復雜度：O(logn)
- 非穩定排序
- 原地排序
使用環境
廣泛
演算法代碼
private static void sort(int[] nums,int start,int end) {
if(nums.length<0)
return;
if(start>=end)
return;
int left=start;
int right=end;
int temp=nums[left];
while (left<right){
while (left<right && nums[right]>=temp)
right--;
nums[left]=nums[right];
while (left<right && nums[left]<=temp)
left++;
nums[right]=nums[left];
}
nums[left]=temp;
sort(nums,start,left-1);
sort(nums,left+1,end);
}
堆排序
代碼思路
利用堆這種資料結構，堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點，
- 將初始待排序關鍵字序列(R1,R2….Rn)構建成大頂堆，此堆為初始的無序區；
- 將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn),且滿足R[1,2…n-1]<=R[n]；
- 由于交換后新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1,R2,……Rn-1)調整為新堆，然后再次將R[1]與無序區最后一個元素交換，得到新的無序區(R1,R2….Rn-2)和新的有序區(Rn-1,Rn)，不斷重復此程序直到有序區的元素個數為n-1，則整個排序程序完成，
復雜度
- 時間復雜度：O(nlogn)
- 空間復雜度：O(1)
- 非穩定排序
- 原地排序
演算法代碼
public static void sort(int[] list) {
//構造初始堆,從第一個非葉子節點開始調整,左右孩子節點中較大的交換到父節點中
for (int i = (list.length) / 2 - 1; i >= 0; i--) {
headAdjust(list, list.length, i);
}
//排序，將最大的節點放在堆尾，然后從根節點重新調整
for (int i = list.length - 1; i >= 1; i--) {
int temp = list[0];
list[0] = list[i];
list[i] = temp;
headAdjust(list, i, 0);
}
}
private static void headAdjust(int[] list, int len, int i) {
int k = i, temp = list[i], index = 2 * k + 1;
while (index < len) {
if (index + 1 < len) {
if (list[index] < list[index + 1]) {
index = index + 1;
}
}
if (list[index] > temp) {
list[k] = list[index];
k = index;
index = 2 * k + 1;
} else {
break;
}
}
list[k] = temp;
}
計數排序
代碼思路
計數排序是一種適合于最大值和最小值的差值不是不是很大的排序，
基本思想：就是把陣列元素作為陣列的下標，然后用一個臨時陣列統計該元素出現的次數，例如 temp[i] = m, 表示元素 i 一共出現了 m 次，最后再把臨時陣列統計的資料從小到大匯總起來，此時匯總起來是資料是有序的，
復雜度
- 時間復雜度：O(n+k)
- 空間復雜度：O(n+k)
- 穩定排序
- 非原地排序
使用環境
其排序速度快于任何比較排序演算法，當k不是很大并且序列比較集中時，計數排序是一個很有效的排序演算法，
演算法代碼
public static void sortCount(int[] arr, int min, int max) {
int len = arr.length;
int[] tem = new int[max - min + 1];
for(int i = 0; i < len; i++) {
tem[arr[i] - min] += 1;
}
for(int i = 0, index = 0; i < tem.length; i++) {
int item = tem[i];
while(item-- != 0) {
arr[index++] = i + min;
}
}
}
桶排序
代碼思路
桶排序是計數排序的升級版，它利用了函式的映射關系，高效與否的關鍵就在于這個映射函式的確定，桶排序 (Bucket sort)的作業的原理：假設輸入資料服從均勻分布，將資料分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序演算法或是以遞回方式繼續使用桶排序進行排），
- 設定一個定量的陣列當作空桶；
- 遍歷輸入資料，并且把資料一個一個放到對應的桶里去；
- 對每個不是空的桶進行排序；
- 從不是空的桶里把排好序的資料拼接起來，
復雜度
- 桶排序最好情況下使用線性時間O(n)，桶排序的時間復雜度，取決與對各個桶之間資料進行排序的時間復雜度，因為其它部分的時間復雜度都為O(n)，很顯然，桶劃分的越小，各個桶之間的資料越少，排序所用的時間也會越少，但相應的空間消耗就會增大
- 時間復雜度：O(n+k)
- 空間復雜度：O(n+k)
- 穩定排序
- 非原地排序
演算法代碼
public static void main(String[] args) {
// 輸入元素均在 [0, 10) 這個區間內
float[] arr = new float[] { 0.12f, 2.6f, 8.8f, 7.6f, 7.2f, 6.3f, 9.0f, 1.6f, 5.6f, 2.4f };
bucketSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bucketSort(float[] arr) {
// 新建一個桶的集合
ArrayList<LinkedList<Float>> buckets = new ArrayList<LinkedList<Float>>();
for (int i = 0; i < 10; i++) {
// 新建一個桶，并將其添加到桶的集合中去，
// 由于桶內元素會頻繁的插入，所以選擇 LinkedList 作為桶的資料結構
buckets.add(new LinkedList<Float>());
}
// 將輸入資料全部放入桶中并完成排序
for (float data : arr) {
int index = getBucketIndex(data);
insertSort(buckets.get(index), data);
}
// 將桶中元素全部取出來并放入 arr 中輸出
int index = 0;
for (LinkedList<Float> bucket : buckets) {
for (Float data : bucket) {
arr[index++] = data;
}
}
}
/**
* 計算得到輸入元素應該放到哪個桶內
*/
public static int getBucketIndex(float data) {
// 這里例子寫的比較簡單，僅使用浮點數的整數部分作為其桶的索引值
// 實際開發中需要根據場景具體設計
return (int) data;
}
/**
* 我們選擇插入排序作為桶內元素排序的方法 每當有一個新元素到來時，我們都呼叫該方法將其插入到恰當的位置
*/
public static void insertSort(List<Float> bucket, float data) {
ListIterator<Float> it = bucket.listIterator();
boolean insertFlag = true;
while (it.hasNext()) {
if (data <= it.next()) {
it.previous(); // 把迭代器的位置偏移回上一個位置
it.add(data); // 把資料插入到迭代器的當前位置
insertFlag = false;
break;
}
}
if (insertFlag) {
bucket.add(data); // 否則把資料插入到鏈表末端
}
}
基數排序
代碼思路
基數排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位，有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序，最后的次序就是高優先級高的在前，高優先級相同的低優先級高的在前，
- 取得陣列中的最大數，并取得位數；
- arr為原始陣列，從最低位開始取每個位組成radix陣列；
- 對radix進行計數排序（利用計數排序適用于小范圍數的特點）；
特點
針對計數排序進行優化的一種演算法，
復雜度
- 時間復雜度：O(kn)
- 空間復雜度：O(n+k)
- 穩定排序
- 非原地排序
演算法代碼
public static void main(String[] args) {
int[] arr = new int[] { 5,789,2138,456,3,1,9,1,13,4984,3 };
radixSort(arr,10000);
System.out.println(Arrays.toString(arr));
}
private static void radixSort(int[] array,int d)
{
int n=1;//代表位數對應的數：1,10,100...
int k=0;//保存每一位排序后的結果用于下一位的排序輸入
int length=array.length;
int[][] bucket=new int[10][length];//排序桶用于保存每次排序后的結果，這一位上排序結果相同的數字放在同一個桶里
int[] order=new int[length];//用于保存每個桶里有多少個數字
while(n<d)
{
for(int num:array) //將陣列array里的每個數字放在相應的桶里
{
int digit=(num/n)%10;
bucket[digit][order[digit]]=num;
order[digit]++;
}
for(int i=0;i<length;i++)//將前一個回圈生成的桶里的資料覆寫到原陣列中用于保存這一位的排序結果
{
if(order[i]!=0)//這個桶里有資料，從上到下遍歷這個桶并將資料保存到原陣列中
{
for(int j=0;j<order[i];j++)
{
array[k]=bucket[i][j];
k++;
}
}
order[i]=0;//將桶里計數器置0，用于下一次位排序
}
n*=10;
k=0;//將k置0，用于下一輪保存位排序結果
}
}
睡眠排序
代碼思路
代碼思路倒是很簡單，就是利用執行緒睡眠來進行排序，讓執行緒睡眠、
特點
娛樂演算法，沒啥特點就是好玩
演算法代碼
public static void sleepSort(int[] array) {
for (int i : array) {
new Thread(()->{
try {
Thread.sleep(i);
} catch (Exception e) {
e.printStackTrace();
}
System.out.println(i);
}).start();
}
}
public static void main(String[] args) {
int[] array = { 10, 30, 50, 60, 100, 40, 150, 200, 70 };
sleepSort(array);
}
隨機排序排序
代碼思路
就是讓系統隨機排序，然后驗證是否有序
特點
巨復雜，看命
演算法代碼
public static void randSortX(int [] array){
List<Integer> list=new ArrayList<>();
for (Integer integer : array) {
list.add(integer);
}
int pre=0;
int index=0;
while(true){
pre=0;
for (index = 1; index < list.size(); index++) {
if(list.get(index)>list.get(pre)){
pre++;
}else{
break;
}
}
if(pre+1==list.size()){
break;
}
Collections.shuffle(list);
}
System.out.println(list.toString());
}
public static void main(String[] args) {
int[] array = { 10, 30, 50, 60, 100, 40, 150, 200, 70 };
randSortX(array);
}
最后
- 如果覺得看完有識訓，希望能給我點個贊，這將會是我更新的最大動力，感謝各位的支持
- 歡迎各位關注我的公眾號【java冢狐】，專注于java和計算機基礎知識，保證讓你看完有所識訓，不信你打我
- 如果看完有不同的意見或者建議，歡迎多多評論一起交流，感謝各位的支持以及厚愛，
——我是冢狐，和你一樣熱愛編程，
歡迎關注公眾號“Java冢狐”獲取最新訊息
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/244541.html
標籤：Java