資訊專(zhuān)欄INFORMATION COLUMN
摘要：總的來(lái)說(shuō)，快速排序也是利用了分治法的思想?？焖倥判虻臅r(shí)間復(fù)雜度為，這是一種不穩(wěn)定的排序方法。以下代碼實(shí)現(xiàn)以二分法的思路對(duì)數(shù)組分組以最左邊最右邊中間三個(gè)數(shù)的中位數(shù)為主元確定主元
以上為思路。
總的來(lái)說(shuō)，快速排序也是利用了分治法的思想。
基本步驟：1.先選擇好合適的主元pivot，
2.然后再把比主元小的元素放到主元的左邊（右邊），把較大的元素放到主元的右邊（左邊），
3.接著再以主元為分界點(diǎn)，把數(shù)組分為兩個(gè)部分，再分別對(duì)兩邊的數(shù)組重復(fù)第二步的操作，
4.最后便實(shí)現(xiàn)了有序排列。
快速排序的時(shí)間復(fù)雜度為O(NlgN)，這是一種不穩(wěn)定的排序方法。
以下代碼實(shí)現(xiàn)
public static void quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1)
quickSort(arr, left, index - 1);
if (index < right)
quickSort(arr, index, right);
}
//以二分法的思路對(duì)數(shù)組分組
private static int partition(int arr[], int left, int right){
int i = left, j = right;
int tmp;
//以最左邊、最右邊、中間三個(gè)數(shù)的中位數(shù)為主元
int pivot = findPivot(arr, left, (left+right)>>1, right);
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
return i;
}
//確定主元
private static int findPivot(int[] nums, int left, int mid, int right){
if(nums[left] > nums[right]) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
if(nums[left] > nums[mid]) {
int temp = nums[left];
nums[left] = nums[mid];
nums[mid] = temp;
}
if(nums[mid] > nums[right]) {
int temp = nums[right];
nums[right] = nums[mid];
nums[mid] = temp;
}
return nums[mid];
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/71240.html
摘要：接下來(lái)我來(lái)說(shuō)明快速排序的思路以及實(shí)現(xiàn)的代碼?？焖倥判蛩悸肥紫仁嵌x一個(gè)變量，把數(shù)組的第一個(gè)元素的值賦給，然后定義兩個(gè)變量指向數(shù)組的第一個(gè)元素和最后一個(gè)元素。 今天突然想寫(xiě)個(gè)排序，以前寫(xiě)過(guò)，然后寫(xiě)了之后一直出錯(cuò)，然后自己百度了一下，看了別人寫(xiě)的方法，自己也嘗試著寫(xiě)了一個(gè)。接下來(lái)我來(lái)說(shuō)明快速排序的思路以及實(shí)現(xiàn)的代碼。 快速排序思路：首先是定義一個(gè)變量key，把數(shù)組的第一個(gè)元素的值賦給key...
摘要：快速排序思路在數(shù)組中尋一中間數(shù)，將比中間數(shù)小的放在左邊，將比中間數(shù)大的放在右邊從左邊開(kāi)始找，找到比中間數(shù)大的，記住，從右邊開(kāi)始找，找到比中間數(shù)小的，然后交換兩邊然后在左邊再尋一中間數(shù)，同坐上面的事，右邊也一樣，然后循環(huán)實(shí)現(xiàn)數(shù)組輸出中間值的位 快速排序 思路 在數(shù)組中尋一中間數(shù)，將比中間數(shù)小的放在左邊，將比中間數(shù)大的放在右邊從左邊開(kāi)始找，找到比中間數(shù)大的，記住，從右邊開(kāi)始找，找到比中間數(shù)...
摘要：排序算法和集合工具類(lèi)排序算法和集合工具類(lèi)。面試官總是問(wèn)排序算法也不是在難為你，而是在考察你的編程功底。你首先要理解多線程不僅僅是和那么簡(jiǎn)單，整個(gè)并發(fā)包下面的工具都是在為多線程服務(wù)。 去年的這個(gè)時(shí)候樓主通過(guò)兩個(gè)月的復(fù)習(xí)拿到了阿里巴巴的 offer，有一些運(yùn)氣，也有一些心得，借著跳槽季來(lái)臨特此分享出來(lái)。簡(jiǎn)單梳理一下我的復(fù)習(xí)思路，同時(shí)也希望和大家一起交流討論，一起學(xué)習(xí)，如果不對(duì)之處歡迎指正一...
摘要：前面介紹了七大算法的思想與實(shí)現(xiàn)步驟，下面來(lái)做一個(gè)歸總。直到無(wú)序區(qū)中的數(shù)為零，結(jié)束排序。步驟以從小到大為例，排序數(shù)組大小為。比較完以后則排序結(jié)束。堆排序思想堆排序是采用樹(shù)的形式的數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行排序的，其中每一個(gè)堆都是完全二叉樹(shù)。 前面介紹了七大算法的思想與實(shí)現(xiàn)步驟，下面來(lái)做一個(gè)歸總。 排序方法 平均復(fù)雜度 最壞復(fù)雜度 最好復(fù)雜度 輔助空間 穩(wěn)定性 直接選擇排序 O(n^2...
閱讀 2163·2023-04-26 00:00
閱讀 3278·2021-09-24 10:37
閱讀 3539·2021-09-07 09:58
閱讀 1531·2019-08-30 15:56
閱讀 2225·2019-08-30 13:11
閱讀 2321·2019-08-29 16:38
閱讀 970·2019-08-29 12:58
閱讀 1889·2019-08-27 10:54
