文章目錄
- 一、冒泡排序
- 1.1 基礎的冒泡排序
- 1.2 冒泡排序的優化（增加flag標志）
- 1.3 冒泡排序的優化（雙向冒泡排序法）
- 二、快速排序
- 2.1 基礎的快速排序
- 2.1.1 雙指標法
- 2.1.2 挖坑法
- 2.1.3 前后指標法
- 2.2 快排的優化（在一定范圍內使用直接插入排序）
- 2.3 快排的優化（使用三數取中法確定基準值）
一、冒泡排序
1.1 基礎的冒泡排序
??演算法思想：從后向前，相鄰兩個元素進行兩兩比較，如果后面的元素的值小于前面元素的值，就交換兩個元素，一趟冒泡下來，最小的元素就會被放到最前面的位置，這樣最多進行n-1趟冒泡，就會把所有的元素全部排好，
??相關代碼如下：
void Bubble_sort(int[] array){
for(int i=0; i<array.length; i++){
for(int j=array.length-1; j>i; j--){
//一趟冒泡排序：從后往前，相鄰兩個元素進行兩兩比較
if(array[j]<array[j-1]){
//如果后面的元素小于前面的元素，就交換
Swap(array, j, j-1);
flag = true;
}
}
}
}
/*
* 時間復雜度：
* 最壞情況：O(n^2) 最好情況(有序時):O(n)
* 空間復雜度：O(1)
* 穩定性：穩定
*/
1.2 冒泡排序的優化（增加flag標志）
??演算法思想：在基礎冒泡排序的演算法上，增加flag標志，用來標記當前冒泡程序中是否發生元素交換，如果在某一趟的比較程序中，發現沒有任何元素移動，就不再進行接下來的比較，
??相關代碼如下：
void Bubble_sort(int[] array){
for(int i=0; i<array.length; i++){
boolean flag = false; //設定一個是否發生元素的標志
for(int j=array.length-1; j>i; j--){
if(array[j]<array[j-1]){
Swap(array, j, j-1);
flag = true;
}
}
if(flag==false)
//該趟沒有發生元素交換，表明該陣列已經有序，直接回傳
return;
}
}
1.3 冒泡排序的優化（雙向冒泡排序法）
??演算法思想：在待排序列的正反兩個方向交替進行掃描，即，第一趟把元素值最大的放在序列的最后面，第二趟把元素值最小的放在序列的最前面，如此反復進行，直到整個待排序列有序，
基本步驟：
??1.在基礎冒泡排序的演算法上進行操作
??2.奇數趟時，從前向后比較相鄰元素的值，如果前面元素的值大于后面元素的值就交換，直到把序列中最大值元素移動到序列的最右端
??3.更新上界
??4.偶數趟時，從后向前比較相鄰元素的值，如果后面元素的值小于前面元素的值就交換，直到把序列中最小值元素移動到序列的最右端
??5.更新下界
??6.直到整個序列有序
相關代碼如下：
void Bubble_sort(int[] array, int left, int right) {
int i = 0;
boolean flag = true; // 用來標記一趟冒泡排序是否發生，初始為true
while (left < right && flag == true) {
flag = false;
// 第一趟先把元素值最大的放在序列的最后面
for (i = left; i < right; i++) {
if (array[i] > array[i + 1]) { // 前一個元素的值大于后一個元素的值
Swap(array, i, i + 1);
flag = true; // 發生了元素交換，flag置為true
}
}
right--; // 更新上界
// 第二趟把元素值最小的放在序列的最前面
for (i = right; i > left; i--) {
if (array[i] < array[i - 1]) { // 后一個元素的值小于前一個元素的值
Swap(array, i, i - 1);
flag = true; // 發生了元素交換，flag置為true
}
}
left++; // 更新下界
}
}
二、快速排序
2.1 基礎的快速排序
??演算法思想：先在待排序列中任取一個元素作為pivot基準值，通過一趟排序把待排序列分成兩個部分:前一部分元素都小于基準值，后一部分元素都大于基準值，此時，pivot就被放到了最終位置上，然后，分別對兩個字表重復上述步驟，直到每一個部分只有一個元素或者為空，
??一趟快速排序實際上是一個交替搜索與排序的程序，
??快排的時間效率與基準值劃分的字表是否對稱有關：當待排序列被劃分為兩個等長的子表時，排序的速度最快，
??當初始表基本有序或者基本逆序時，快排的時間效率最低（為一棵單支二叉樹）
2.1.1 雙指標法
基本步驟：
??1.把第一個元素取下來，作為pivot
??2.一個指標從尾開始找比pivot小的數
??3.另一個指標從頭開始找比pivot大的數
??4.如果找到，就交換兩個數
??5.最后，把pivot和尾指標指向的數交換（此時，pivot被放到其最終位置）
相關代碼如下：
//基于分治的思想
int Partition(int[] array, int left, int right){
int pivot = array[left];
while(left<right){
while(left<right && array[right]>=pivot){
right--;
}
//找到了比pivot小的數，交換，放到前面
Swap(array, right, left);
while(left<right && array[left]<pivot){
left++;
}
//找到了比pivot大的數，交換，放到后面
Swap(array, left, right);
}
//找到了pivot的最終位置
array[left] = pivot;
return left;
}
void Qucik_sort(int[] array, int left, int right){
if(left<right){
//先找基準值
int partition = Partition(array, left, right);
//以基準值為界，依次對左右兩個字表進行遞回排序
Qucik_sort(array, left, partition-1);
Qucik_sort(array, partition+1, right);
}
}
/*
* 快速排序時間復雜度：
* 最壞情況：O(n^2) 最好情況(有序時):O(nlogn)
* 空間復雜度：最大遞回深度為n，最小遞回深度為logn
* 最壞情況：O(n) 最好情況(有序時):O(nlogn)
* 穩定性：不穩定
*/
2.1.2 挖坑法
基本步驟：
??1.把第一個元素的值pivot拿出來，把第一個位置當做坑
??2.一個指標從尾開始找比pivot小的數，找到以后，放在坑里，該指標所在的位置作為新的坑
??3.另一個指標從頭開始找比pivot大的數，找到以后，放在坑里，該指標所在的位置作為新的坑
??4.直到頭尾指標相遇
??5.然后把第一個資料放在最后一個坑里
相關代碼如下：
int Partition1(int[] array, int left, int right) {
int pivot = array[left]; // 取第一個元素作為坑
while (left < right) {
//從尾開始找比pivot小的數，找到以后，放在坑里，該指標所在的位置作為新的坑
while (array[right] >= pivot && left < right) {
right--;
}
array[left] = array[right];
//從頭開始找比pivot大的數，找到以后，放在坑里，該指標所在的位置作為新的坑
while (array[left] < pivot && left < right) {
left++;
}
array[right] = array[left];
}
// 把第一個資料放在最后一個坑里
array[left] = pivot;
return left;
}
2.1.3 前后指標法
基本步驟：
??1.取第一個元素的值pivot，讓prev指向第一個資料，讓cur指向第二個資料
??2.讓cur從第二個資料開始依次遍歷每一個資料，如果cur所指向的資料比pivot小，就把它和prev++所指向的資料交換（要保證prev++ != cur）
??3.最后，讓prev所指向的資料和pivot交換
相關代碼如下：
int Partition2(int[] array, int left, int right) {
// 取第一個元素為pivot，讓prev指向第一個資料，讓cur指向第二個資料
int pivot = array[left];
int prev = left;
int cur = left + 1;
// 讓cur依次遍歷每一個元素
while (cur <= right) {
if (array[cur] <= pivot && prev++ != cur) {
Swap(array, cur, prev);
}
++cur;
}
Swap(array, prev, left);
return prev;
}
2.2 快排的優化（在一定范圍內使用直接插入排序）
void Qucik_sort2(int[] array, int left, int right){
if(left >= right)
return;
//優化方式一:在right-left+1<=100范圍里，使用直接插入排序
if(right-left+1 <= 100){
Insert_sort(array, left, right);
}
if(left < right){
int partition = Partition_1(array, left, right);
Qucik_sort2(array, left, partition-1);
Qucik_sort2(array, partition+1, right);
}
}
2.3 快排的優化（使用三數取中法確定基準值）
??基本思想：利用三數取中法，把中間的元素換到最左邊(相當于傳統劃分方法中的第一個位置上的元素)，一般是在基本有序的范圍內使用，
即，實作array[mid]<=array[left]<=array[right]的效果，
??相關代碼如下：
void three_num_mid(int[] array, int left, int right){
int mid = (left+right)/2;
//mid下標的為中間元素，使其放到第一個位置，作為基準值
if(array[mid] > array[left]){
Swap(array, mid, left);
}
if(array[mid] > array[right]){
Swap(array, mid, right);
}
if(array[left] > array[right]){
Swap(array, left, right);
}
}
void Quick_sort3(int[] array, int left, int right) {
if (left >= right)
return;
if (right - left + 1 <= 100) {
Insert_sort(array, left, right);
}
three_num_mid(array, left, right);
int partition = Partition_1(array, left, right);
Quick_sort3(array, left, partition - 1);
Quick_sort3(array, partition + 1, right);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/330315.html
標籤：其他