排序算法-归并排序与快速排序

归并排序与快速排序

快速排序是利用的递归思想：选取一个基准数，把小于基准数的放左边 大于的放右边直到整个序列有序 。快排分割函数 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;
}