歸并排序與快速排序
快速排序是利用的遞歸思想：選取一個基準數，把小于基準數的放左邊 大于的放右邊直到整個序列有序 。快排分割函數 O(lognn), 空間 :沒有額外開辟新的數組但是遞歸樹調用函數會占用棧內存 O(logn) 。
歸并排序：在遞歸返回的過程中保證每個返回的子集都是有序的。時間O(lognn)，空間：O(n)。
歸并排序
#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;
//在歸 的過程中 進行數據的合并 達到排序的效果
//時間O(logn*n) 空間：O(n)
//遞歸排序
void _merge(int arr[], int left, int mid, int right){int *p = new int[right - left + 1]; int idx = 0; int i = left;int j = mid + 1;//開始數據合并 while(i <= mid && j <= right){if(arr[i] <= arr[j]){p[idx++] = arr[i++];}else{p[idx++] = arr[j++];}}//左端有剩余 while(i <= mid){p[idx++] = arr[i++];} //右端有剩余while(j <= right){p[idx++] = arr[j++];} //將合并后的數據拷貝給原數組for(i = left, j = 0; i <= right ; ++i, ++j){arr[i] = p[j];}delete []p;
} //歸并排序遞歸接口函數
void _mergeSort(int arr[], int left, int right){// 遞歸結束條件if(left >= right) return; int mid = (left + right) / 2;//先傳遞 _mergeSort(arr, left, mid);_mergeSort(arr, mid + 1, right);//再歸并 額外的內存空間 小段有序 和并為 大段有序_merge(arr, left, mid, right);
} void _mergeSort(int arr[] , int length){return _mergeSort(arr, 0, length - 1);
}int main(){int arr[10];int length = 10;srand(time(NULL));for(int i = 0 ; i < length ; ++i){arr[i] = rand() % 100 + 1;cout<<arr[i]<<" "; }cout<<endl;_mergeSort(arr,length); for(int i = 0 ; i < length ; ++i){cout<<arr[i]<<" "; }return 0;
}
快速排序
#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;
//快速排序思想：選取一個基準數，把小于基準數的放左邊 大于的放右邊 直到整個序列有序
//從數組左右兩邊都找 找到一個停下來換另外一邊
//快排優化思想：隨著快排算法的執行，數據越來越有序，在一定范圍內，可以采用插入排序代替快速排序 //快排分割函數 O(logn*n) 空間 :沒有額外開辟新的數組但是遞歸樹調用函數會占用棧內存 O(logn)
int partation(int arr[] , int begin , int end){int val = arr[begin];int i = begin;int j = end;while(i < j){while(i < j && arr[j] > val)j--;//找到小于基準數 if(i < j){arr[i] = arr[j];i++; }while(i < j && arr[i] < val){i++;}//大于的基準數 if(i < j){arr[j] = arr[i];j--;}} arr[i] = val;return i;
}
//快排的遞歸接口
void _fast(int arr[] , int begin , int end){if(begin >= end) return; //遞歸結束條件//在區間做一次快排int pos = partation(arr, begin, end);//對基準數的左邊快排_fast(arr, begin , pos - 1); //對基準數的右邊做快排 _fast(arr, pos + 1 , end);}void _fast(int arr[] , int length){return _fast(arr, 0 , length - 1);
}int main(){int arr[10];int length = 10;srand(time(NULL));for(int i = 0 ; i < length ; ++i){arr[i] = rand() % 100 + 1;cout<<arr[i]<<" "; }cout<<endl;_fast(arr,length); for(int i = 0 ; i < length ; ++i){cout<<arr[i]<<" "; }return 0;
}
