在日常開發中經常會遇到一類問題,就是對一個集合的數據進行排序
掌握一些排序算法,對於日常開發是非常有幫助
今天介紹一下快速排序法
01算法邏輯
02時間複雜度
由上圖邏輯可以得出,參照遞歸表達式漸進複雜度分析
快速排序的時間複雜度遞歸表達式為,其中a=2,b=2,d=1
由算法導論的主定理可以推導出,快速排序的時間複雜度為
03空間複雜度
由上圖邏輯可以得出,參照遞歸表達式漸進複雜度分析
快速排序的空間複雜度遞歸表達式為,其中a=2,b=2,d=1
由算法導論的主定理可以推導出,快速排序的空間複雜度為
04java代碼實現
public int[] sortByQuick(int[] data, int start, int end) {
int i = start;
int j = end;
//Todo: 如果比較後的左側位置和右側位置不等,則繼續執行比較規則
while (i != j) {
//Todo: 執行右側比較規則,返回交換後的下標
j = this.quick_right(data, i, j);
if (j != start) {
//右側比較規則執行交換後,左側下標+1
i++;
}
//Todo: 執行左側比較規則,返回交換後的下標
i = this.quick_left(data, i, j);
}
//Todo: 如果拆分後存在左側數據的話,則繼續從左側遞歸排序
if (i != start && start != i - 1) {
data = this.sortByQuick(data, start, i - 1);
}
//Todo: 如果拆分後存在右側數據的話,則繼續從右側遞歸排序
if (j != end && j + 1 != end) {
data = this.sortByQuick(data, j + 1, end);
}
return data;
}
public int quick_right(int[] data, int start, int end) {
for (int k = end; k > start; k--) {
if (data[start] > data[k]) {
int temp = data[k];
data[k] = data[start];
data[start] = temp;
return k;
}
}
return start;
}
public int quick_left(int[] data, int start, int end) {
for (int k = start; k < end; k++) {
if (data[k] > data[end]) {
int temp = data[k];
data[k] = data[end];
data[end] = temp;
return k;
}
}
return end;
}
05小結
今天主要介紹了單集合排序的一種排序算法——快速排序
小夥伴們都了解了嗎?
下次小Top將繼續介紹單集合排序算法
對於今天的內容有任何疑問或問題,歡迎留言或討論 ^-^