摘要:一常見的排序算法及時間復雜度二各排序算法的理解及實現冒泡排序算法描述比較相鄰元素,如果第一個比第二個大,交換位置,這樣每經過一趟就冒出一個最大的動圖演示代碼實現快速排序算法描述從數列中挑出一個元素,稱為基準從左向右找比這個第一個比這個基
一.常見的排序算法及時間復雜度 二.各排序算法的理解及實現 1.冒泡排序(Bubble Sort)O(n2)
(1)算法描述
比較相鄰元素,如果第一個比第二個大,交換位置,這樣每經過一趟就冒出一個最大的
(2)動圖演示
(3)代碼實現
</>復制代碼
public static int[] bubbleSort(int arr[]){
int len = arr.length;
for(int i = 0;iarr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
2.快速排序 O(nlog2n)
(1)算法描述
從數列中挑出一個元素,稱為"基準"(pivot)
從左向右找比這個第一個比這個基準大的數,從右往左找第一個比這個基準小的數,找到后互換位置
繼續在此基礎上執行第二步,直到兩個尋找指針相遇
遞歸的(recursive)把小于基準值的序列和大于基準值的序列排序
(2)動圖演示
</>復制代碼
public static void quickSort(int[]arr, int left,int right) {
if(left>right){return; }//遞歸的出口
int i = left,j = right;
int pivot = arr[left];//找到基準
while (i < j) {
//從右向左找第一個比基準值小的數
while (i < j && arr[j] >= pivot) {
j--;
}
//從左向右找第一個比基準值大的數
while (i < j && arr[i] <= pivot) {
i++;
}
//兩面都找到后互換位置
if (i < j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
//left=right時于基準值互換
int tmp = arr[j];
arr[j] = arr[left];
arr[left] = tmp;
//分別遞歸的調用基準值的左邊和右邊
quickSort(arr,left,i-1);
quickSort(arr,i+1,right);
}
3.簡單插入排序 O(n2)
(1)算法描述
從第二個元素開始(因為認為第一個元素已經有序)向前掃描
如果前一個數小于當前元素,繼續跳到下一個元素開始向前掃描
如果前一個數大于當前元素,繼續向前掃描,直到找到小于這個數的元素,插到它的后面
(2)動圖演示
(3)代碼實現
</>復制代碼
public static void insertSort(int[] array){
int len = array.length;
for(int i = 1;i0 && array[j-1]>temp;j--){
//如果比待插入數大 ,向右移
array[j] = array[j-1];
}
//如果比帶插入數小,插在該數后面
array[j] = temp;
}
4.希爾排序 O(nlogn)
(1)算法描述
其實就是對插入排序進行了優化,先對相同間隔的一組數進行插入排序,使序列基本有序,再進行間隔為1的插入排序時,減少工作量。(代碼實現可對照插入排序,其實就是多了一組循環)
(2)動圖演示
(3)代碼實現
</>復制代碼
public static void shellSort(int[] array){
int len= array.length;
int gap;//增量長度
for(gap = len/2;gap>0;gap/=2){
for(int i = gap;i gap && array[j - gap] > temp; j-=gap) {
//如果比待插入數大 ,向右移
array[j] = array[j - gap];
}
//如果比待插入數小,插在該數后面
array[j] = temp;
}
}
}
5.簡單選擇排序 O(n2)
(1)算法描述
將序列劃分為有序區和無序區(初始狀態有序區為空)
遍歷無序區,選出最小的元素,放到有序區
(2)動圖演示
(3)代碼實現
</>復制代碼
public static int[] selectSort(int array[]){
for(int i=0;i
6.堆排序
(1)算法描述
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/69107.html
摘要:算法描述冒泡排序是一種簡單的排序算法。算法描述和實現一般來說,插入排序都采用在數組上實現。平均情況希爾排序年發明第一個突破的排序算法是簡單插入排序的改進版它與插入排序的不同之處在于,它會優先比較距離較遠的元素。 前言 讀者自行嘗試可以想看源碼戳這,博主在github建了個庫,讀者可以Clone下來本地嘗試。此博文配合源碼體驗更棒哦~~~ 個人博客:Damonare的個人博客 原文地址:...
摘要:數據結構和算法樹快速排序,堆排序,插入排序其實八大排序算法都應該了解一致性算法,一致性算法的應用的內存結構。如何存儲一個的。八大排序算法一定要手敲一遍快排,堆排尤其重要。面試是一個雙向選擇的過程,不要抱著畏懼的心態去面試,不利于自己的發揮。 前言 16年畢業到現在也近兩年了,最近面試了阿里集團(菜鳥網絡,螞蟻金服),網易,滴滴,點我達,最終收到點我達,網易offer,螞蟻金服二面掛掉,...
摘要:前面介紹了七大算法的思想與實現步驟,下面來做一個歸總。直到無序區中的數為零,結束排序。步驟以從小到大為例,排序數組大小為。比較完以后則排序結束。堆排序思想堆排序是采用樹的形式的數據結構來進行排序的,其中每一個堆都是完全二叉樹。 前面介紹了七大算法的思想與實現步驟,下面來做一個歸總。 排序方法 平均復雜度 最壞復雜度 最好復雜度 輔助空間 穩定性 直接選擇排序 O(n^2...
閱讀 828·2023-04-25 22:13
閱讀 2340·2019-08-30 15:56
閱讀 2226·2019-08-30 11:21
閱讀 656·2019-08-30 11:13
閱讀 2020·2019-08-26 14:06
閱讀 1958·2019-08-26 12:11
閱讀 2289·2019-08-23 16:55
閱讀 538·2019-08-23 15:30