- // 分治思想
- // 分类 ---------------- 内部比较排序
- // 数据结构 ------------ 数组
- // 最差时间复杂度 ------ 每次选取的基准都是最大或者最小的元素, 导致每次只划分出
- // 了一个分区需要进行 n-1 次划分才能结束递归, 时间复杂度为 O(n^2)
- // 最优时间复杂度 ------ 每次选取的基准都是中位数, 这样每次都均匀的划分出两个区域
- // 只需要 logn 次划分就能结束递归, 时间复杂度为 O(nlogn)
- // 平均时间复杂度 ------O(nlogn)
- // 所需辅助空间 -------- 主要是递归造成的栈空间的使用(用来保存 left 和 right 等局部变量)
- // 取决于递归树的深度, 一般为 O(logn), 最差为 O(n)
- // 稳定性 --------------- 不稳定
- void Swap(int arr[],int i,int j)
- {
- int tmp = arr[i];
- arr[i] = arr[j];
- arr[j] = tmp;
- }
- int Partition(int arr[],int left,int right)// 划分函数
- {
- int pivor = arr[right];// 每次都选择最后一个元素做基准
- int tail =left -1;//tail 为小于基准的子数组最后一个元素的 索引
- for(int i = left;i <right;++i)// 遍历基准以外的其他元素
- {
- if(arr[i] <= pivor)
- {
- Swap(arr,++tail,i);
- }
- }
- Swap(arr,tail+1,right);// 该操作有可能把后边元素的稳定性打乱
- return tail + 1;
- }
- void QuickSort(int *arr,int left,int right)
- {
- if(left>= right)
- {
- return ;
- }
- int pivor_index = Partition(arr,left,right);
- QuickSort(arr,left,pivor_index-1);
- QuickSort(arr,pivor_index+1,right);
- }
- #include<stdio.h>
- // 分治思想
- // 分类 ---------------- 内部比较排序
- // 数据结构 ------------ 数组
- // 最差时间复杂度 ------ 每次选取的基准都是最大或者最小的元素, 导致每次只划分出
- // 了一个分区需要进行 n-1 次划分才能结束递归, 时间复杂度为 O(n^2)
- // 最优时间复杂度 ------ 每次选取的基准都是中位数, 这样每次都均匀的划分出两个区域
- // 只需要 logn 次划分就能结束递归, 时间复杂度为 O(nlogn)
- // 平均时间复杂度 ------O(nlogn)
- // 所需辅助空间 -------- 主要是递归造成的栈空间的使用(用来保存 left 和 right 等局部变量)
- // 取决于递归树的深度, 一般为 O(logn), 最差为 O(n)
- // 稳定性 --------------- 不稳定
- void Swap(int arr[],int i,int j)
- {
- int tmp = arr[i];
- arr[i] = arr[j];
- arr[j] = tmp;
- }
- int Partition(int arr[],int left,int right)// 划分函数
- {
- int pivor = arr[right];// 每次都选择最后一个元素做基准
- int tail =left -1;//tail 为小于基准的子数组最后一个元素的 索引
- for(int i = left;i <right;++i)// 遍历基准以外的其他元素
- {
- if(arr[i] <= pivor)
- {
- Swap(arr,++tail,i);
- }
- }
- Swap(arr,tail+1,right);// 该操作有可能把后边元素的稳定性打乱
- return tail + 1;
- }
- void QuickSort(int *arr,int left,int right)
- {
- if(left>= right)
- {
- return ;
- }
- int pivor_index = Partition(arr,left,right);
- QuickSort(arr,left,pivor_index-1);
- QuickSort(arr,pivor_index+1,right);
- }
- // 分类 ------------- 内部比较排序
- // 数据结构 --------- 数组
- // 最差时间复杂度 ---O(n^2)
- // 最优时间复杂度 --- O(n^2)
- // 平均时间复杂度 ----O(n^2)
- // 所需辅助空间 ------O(1)
- // 稳定性 ------------ 不稳定
- void select_sort(int arr[],int len)
- {
- for(int i = 0; i <len -1;++i)
- {
- int min = i;
- for(int j = i+1;j < len;j++)
- {
- if(arr[min]> arr[j])
- {
- min = j;
- }
- }
- if(min != i)
- {
- swap(arr,min,i);
- }
- }
- return ;
- }
- // 分类 -------------- 内部比较排序
- // 数据结构 ---------- 数组
- // 最差时间复杂度 --- 根据步长序列的不同而不同, 已知最好的为 O(n(logn)^2)
- // 最优时间复杂度 ----O(n)
- // 平均时间复杂度 ---- 根据步长的不同而不同
- // 所需辅助空间 ------O(1)
- // 稳定性 ------------ 不稳定
- void ShellSort(int *arr,int len)
- {
- int h = 0;
- while(h <= len)
- {
- h = 3*h+1;
- }
- while(h>=1 )
- {
- for(int i = h;i <len;++i)
- {
- int j = i-h;
- int get = arr[i];
- while(j>=0 && arr[j]> get)
- {
- arr[j+h] = arr[j];
- j = j-h;
- }
- arr[j+h] = get;
- }
- h = (h-1)/3;
- }
- }
- // 分类 ---------------------- 内部比较排序
- // 数据结构 ------------------ 数组
- // 最差时间复杂度 -----------O(nlogn)
- // 最优时间复杂度 -----------O(nlogn)
- // 平均时间复杂度 -----------O(nlogn)
- // 所需辅助空间 -------------O(n)
- // 稳定性 ------------------- 稳定
- void Merge(int *arr,int left,int mid,int right)
- {
- int len = right - left + 1;
- int *tmp = new int[len];// 辅助空间
- int index = 0;
- int i = left;// 前一数组的起始元素
- int j = mid + 1;// 后一数组的起始元素
- while(i <=mid && j <= right)
- {
- tmp[index++] = arr[i] <= arr[j]? arr[i++]:arr[j++];// 等号保证稳定性
- }
- while(i <= mid)
- {
- tmp[index++] = arr[i++];
- }
- while(j <= right)
- {
- tmp[index++] = arr[j++];
- }
- for(int k = 0; k <len; k++)
- {
- arr[k] = tmp[k];
- }
- }
- ///////////////////////////////////////////////////
- void MergeSortInteration(int *arr,int len)// 非递归 (迭代) 实现的归并排序(自底向上)
- {
- int left,mid,right;// 子数组索引, 前一个为 arr[left...mid],
- // 后一个为 arr[mid+1...right]
- for(int i = 1;i < len; i*=2)
- {
- left = 0;
- while(left+i < len)
- {
- mid = left +i -1;
- right = mid + i < len?mid+i:len-1;// 后一个数组大小可能不够
- Merge(arr,left,mid,right);
- left =right + 1;
- }
- }
- }
- ////////////////////////////////////////////
- void MergeSortRecursion(int *arr,int left,int right)// 递归实现的归并(自顶向下)
- {
- if(left == right)// 当待排序的序列长度为 1 时, 递归开始回溯, 进行 Merge 操作
- {
- return;
- }
- int mid = (left + right)/2;
- MergeSortRecursion(arr,left,mid);
- MergeSortRecursion(arr,mid+1,right);
- Merge(arr,left,mid,right);
- }
- // 分类 --------------- 内部比较排序
- // 数据结构 ----------- 数组
- // 最差时间复杂度 -----O(n^2)
- // 最优时间复杂度 -----O(nlogn)
- // 平均时间复杂度 -----O(n^2)
- // 所需辅助空间 -------O(1)
- // 稳定性 ------------- 稳定
- void InsertSortDichotomy(int *arr,int len)
- {
- for(int i = 1;i < len;++i)
- {
- int tmp = arr[i];
- int left = 0;
- int right = i-1;
- while(left <= right)
- {
- int mid = (left + right)/2;
- if(arr[mid]> tmp)
- right = mid -1;
- else
- left = mid + 1;
- }
- for(int j = i-1;j>= left;--j)
- {
- arr[j+1] = arr[j];
- }
- arr[left] = tmp;
- }
- }
- // 分类 -------------- 内部比较排序
- // 数据结构 ---------- 数组
- // 最差时间复杂度 ---- 最坏情况为输入序列式降序排列的, 此时时间复杂度为 O(n^2)
- // 最优时间复杂度 ---- 最优情况是输入序列是升序排列的, 此时时间复杂度为 O(n)
- // 平均时间复杂度 ----O(n^2)
- // 所需辅助空间 ------O(1)
- // 稳定性 ------------ 稳定
- void InsertionSort(int *arr,int len)
- {
- for(int i = 1; i <len;++i)
- {
- int tmp = arr[i];
- int j =i-1;
- while(j>=0 && arr[j]>tmp)
- {
- arr[j+1] = arr[j];
- j--;
- }
- arr[j+1] = tmp;
- }
- }
- // 堆排序
- void AdjustArr(int *arr,int index,int len)
- {
- int tmp = arr[index];
- for(int i = 2*index+1;i <len;i=i*2+1)
- {
- if(i+1 < len && arr[i+1]>arr[i])
- {
- i+=1;
- }
- if(arr[i]> tmp)
- {
- arr[index] = arr[i];
- index = i;
- }
- else
- {
- break;
- }
- }
- arr[index ] = tmp;
- }
- void HeapSort(int *arr,int len)
- {
- for(int i = len/2-1;i>=0;--i)
- {
- AdjustArr(arr,i,len);
- }
- for(int j = len - 1;j> 0;--j)
- {
- Swap(arr,j,0);
- AdjustArr(arr,0,j);
- }
- }
- // 冒泡排序
- void BubbleSort(int arr[],int len)
- {
- for(int i = 0;i <len-1;i++)
- {
- for(int j = 0; j < len-i-1;j++)
- {
- if(arr[j]> arr[j+1])
- Swap(arr,j,j+1);
- }
- }
- }
- void BubbleSort(int arr[],int len)
- {
- for(int i = 0;i <len-1;i++)
- {
- for(int j = 0; j < len-i-1;j++)
- {
- if(arr[j]> arr[j+1])
- Swap(arr,j,j+1);
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2540742.html