排序算法
#include<iostream>
#include<algorithm>
using namespace std;
//排序算法(时间复杂度:最好,最坏,平均)
//插入排序{O(n),O(n^2),O(n^2)}{稳定}{链表也可使用}
void Insert_Sort(int arr[],int n){
int temp = 0,i,j;
for(int i = 1;i<n;i++){
if(arr[i]<arr[i-1]){
temp = arr[i];
for(j = i-1;j>=0&&arr[j]>temp;j--){
arr[j+1] = arr[j];
}
arr[j+1] = temp;
}
}
}
//折半插入排序{o(n^2)}
void Insert02_Sort(int arr[],int n){
int i,j,temp,low,high,mid;
for(i = 1;i<n;i++){ //一次将数组中的元素插入已排列的序列
temp = arr[i];
low = 0;
high = i-1;
while(low<=high){ //折半查找
mid = (low+high)/2;
if(arr[mid]>temp){ //查找左半子表
high = mid-1;
}else{
low = mid+1; //查找右半子表
}
}
for(j = i-1;j>=low;j--){
arr[j+1] = arr[j]; //后移操作
}
arr[low] = temp; //插入操作
}
}
//希尔排序{O(n^1.3),O(n^2),不稳定,仅适用于顺序表}
void ShellSor(int arr[],int n){
int d,i,j;
for(d = n/2;d>=1;d = d/2){ //步长变换
for(i = d+1;i<=n;i++){
if(arr[i]<arr[i-d]){ //需要将arr[i]插入有序增量列表
arr[0] = arr[i]; //暂存在arr[0]
for(j = i-d;j>0&&arr[0]<arr[j];j-=d){
arr[j+d] = arr[j]; //记录后移,查找插入的位置
}
arr[j+d] = arr[0]; //插入
}
}
}
}
//冒泡排序{O(n),O(n^2),稳定,可以用于链表}
void BubbleSort(int arr[],int n){
for(int i = 0;i<n-1;i++){
bool tag = false;
//标志位,如果某一趟排序没有交换。则说明已经有序
for(int j = n-1;j>i;j--){
if(arr[j]<arr[j-1]){
swap(arr[j],arr[j-1]);
tag = true;
}
}
if(tag == false) return;
}
}
//快速排序{O(nlog2n),O(n^2),不稳定}
//本身有序的时候效率最低
//优化:对于基准的选取尽量选取中间大的
int Temptition(int arr[],int low,int high){
//low所指元素作为基准元素
int temp = arr[low];
//此while循环确定基准元素对应的位置
while(low<high){
//比基准大的不动,一直向左找到小于基准的元素
while(low<high&&arr[high]>=temp){
high--;
}
//比基准小的移到low的位置
arr[low] = arr[high];
//比基准小的不动,一直向左找到大于基准的元素
while(low<high&&arr[low]<=temp){
low++;
}
//比基准大的移到high的位置
arr[high] = arr[low];
}
//将基准元素插入的相应位置
arr[low] = temp;
//将最后停留的位置返回
return low;
}
void QuickSort(int arr[],int low,int high){
if(low<high){
//获取上一次快排最后插入的位置
int temp = Temptition(arr,low,high);
//划分左侧,继续使用快排
QuickSort(arr,low,temp-1);
//划分右侧,继续使用快排
QuickSort(arr,temp+1,high);
}
}
//简单选择排序{O(n^2),不稳定,链表也可以使用}
void SelectSort(int arr[],int n){
for(int i = 0;i<n-1;i++){
int min = i;
for(int j = i+1;j<n;j++){
if(arr[j]<arr[min]){
min = j;
}
}
if(min!=i){
swap(arr[i],arr[min]);
}
}
}
//堆排序{建堆的时候O(n),排序的时候O(nlog2n),不稳定}
void HeadAdjust(int arr[],int k,int len){
//arr[0]暂存子树的根节点
arr[0] = arr[k];
//沿key较大的子节点向下筛选
for(int i = 2*k;i<=len;i=i*2){
if(i<len&&arr[i]<arr[i+1]){
i++; //取key较大的子节点的下标
}
if(arr[0]>=arr[i]) break; //筛选结果
else{
arr[k] = arr[i]; //将arr[i]调整到双亲结点上
k = i; //修改l值,以便继续向下筛选
}
}
arr[k] = arr[0]; //被筛选结点的值放入最终位置
}
//建立大根堆
void BuildMaxHeap(int arr[],int len){
//调整每一个分支节点的堆
for(int i = len/2;i>0;i--){
HeadAdjust(arr,i,len);
}
}
void HeapSort(int arr[],int len){
BuildMaxHeap(arr,len);
for(int i = len;i>1;i--){
swap(arr[i],arr[1]);
HeadAdjust(arr,1,i-1);
}
}
//归并排序{O(nlog2n),稳定的}
int n = 10;
//另外开辟的数组,用来临时存储分开的数组
int *arr02 = new int [n];
//合并操作
void Merge(int arr[],int low,int mid,int high){
int i,j,k;
//将数组赋值到新开辟的数组
for(k = low;k<=high;k++){
arr02[k] = arr[k];
}
//按照两个分开的部分第一个数值的大小放到原数组中
//k指的是原数组,i,j分别指向分开的两个部分
for(i = low,j = mid+1,k = i;i<=mid&&j<=high;k++){
if(arr02[i]<=arr02[j]){
arr[k] = arr02[i++];
}else{
arr[k] = arr02[j++];
}
}
//两个部分中多出来的一部分也要放进去
while(i<=mid){
arr[k++] = arr02[i++];
}
while(j<=high){
arr[k++] = arr02[j++];
}
}
void MergeSort(int arr[],int low,int high){
if(low<high){
int mid = (low+high)/2;
MergeSort(arr,low,mid);
MergeSort(arr,mid+1,high);
Merge(arr,low,mid,high);
}
}
//基数排序{O(d(n+r)),n个队列,链式存储实现,稳定的}
int main(){
int arr[10] = {3,5,7,1,2,8,6,10,9,4};
HeapSort(arr,10);//0
SelectSort(arr,10);
QuickSort(arr,0,9);
Insert_Sort(arr,10);
ShellSor(arr,10);//0
for(int i = 0;i<10;i++){
cout<<arr[i]<<endl;
}
return 0;
}
版权声明:本文为Manner11原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。