#include<iostream>
using namespace std;
void out_print(int arr[],int len)
{
for(int i(0);i<len;i++)
{
cout<<arr[i]<<"\t";
}
}
void swap(int &i,int &j)//交換函式
{
int k;
k=j;
j=i;
i=k;
}
/*void Straigthinsertsort(int arr[],int len)//直接插入排序
{
for(int i(1);i<len;i++)
{
int e=arr[i];//暫存要插入的數字
for(int j=i-1;e<arr[j]&&i>=0;j--)
{
arr[j+1]=arr[j];
}
arr[j+1]=e;
}
}
//直接插入排序的時間復雜度為O(n^2)*/
/*void ShellInsert(int arr[],int len,int incr)//incr為增量
//希爾排序的思想為先將整個序列分割為若干個子序列，等序列中元素基本有序，再對全體元素進行一次插入排序
{ //cout<<incr<<"\t";
for(int i=incr;i<len;i++)
{
int e=arr[i];
for(int j=i-incr;e<arr[j]&&j>=0;j-=incr)
{
arr[j+incr]=arr[j];
}
arr[j+incr]=e;
}
}
void shellSort(int arr[],int len,int t,int inc)//t為增量長度inc為增量陣列
{
for(int k(0);k<=t;k++)
{
ShellInsert(arr,len,inc);
inc--;
}
out_print(arr,len);
}*/
/*int partition(int arr[],int low,int high)//快速排序，中心思想：任選一個數字將比他大的數放在右邊比他小的數放在左邊，在依次對其排序
{
while(low<high)
{
while(low<high&&arr[low]<=arr[high])
high--;
swap(arr[low],arr[high]);
while(low<high&&arr[low]<=arr[high])
low++;
swap(arr[low],arr[high]);
}
return low;
}//操作結果為回傳軸的位置
void quitsorthelp(int arr[],int low,int high)//完成快速排序,利用遞回
{
if(low<high)
{
int par=partition(arr,low,high);
quitsorthelp(arr,low,par-1);
quitsorthelp(arr,par+1,high);
}
}
void QuitSort(int arr[],int len)
{
quitsorthelp(arr,0,len-1);
out_print(arr,len);
}*///快速排序的平均時間復雜度O(nlogn),當陣列有序時為O(n^2)和冒泡排序一樣
/*void SimpleSelectSort(int arr[],int len)//簡單選擇排序，在n-1次排序中選擇最小的數作為第i個數,時間復雜度為O(n^2)
{
for(int i(0);i<len;i++)
{
int index=i;
for(int j=i+1;j<len;j++)
{
if(arr[j]<arr[index])
index=j;
}
swap(arr[i],arr[index]);
}
out_print(arr,len);
}*/
//堆排序是一種基于選擇排序的先進排序演算法
/*void SiftAdjust(int arr[],int low,int high)
//調整arr[low]，使其成為大頂堆
{
for(int f=low,i=2*low+1;i<high;i=2*i)
{
if(i<high&&arr[i]<arr[i+1])
i++;
if(i<high&&arr[f]>arr[i])
break;
swap(arr[f],arr[i]);
f=i;
}
}
void HeapSort(int arr[],int len)
{
for(int i=(len-2)/2;i>=0;i--)//調整堆為大頂堆，
{
SiftAdjust(arr,i,len-1);
}
//out_print(arr,len);
for(i=len-1;i>=0;i--)//交換頂堆元素與最后一個元素，重新調整堆為大頂堆
{
swap(arr[0],arr[i]);
SiftAdjust(arr,0,i-1);
}
out_print(arr,len);
}*/
//歸并排序
/*void SimpleSort(int arr[],int low,int mid,int high)//將兩個有序陣列進行排序
{
int *elem=new int[high-low+1];
int k=0;
for(int i=low,j=mid+1;i<=mid&&j<=high;k++)
{
if(arr[i]<arr[j])
{
elem[k]=arr[i];
i++;
}else{
elem[k]=arr[j];
j++;
}
}
for(;i<=mid;i++)
{
elem[k]=arr[i];
}
for(;j<=high;j++)
{
elem[k]=arr[j];
}
for(i=low,k=0;i<=high;i++,k++)
{
arr[i]=elem[k];
}
delete []elem;
}
void SimpleMergeSort(int arr[],int low,int high)//利用遞回將陣列進行排序
{
if(low<high)
{
int mid=(low+high)/2;
SimpleMergeSort(arr,low,mid);
SimpleMergeSort(arr,mid+1,high);
SimpleSort(arr,low,mid,high);
}
}
void MergeSort(int arr[],int len)
//歸并排序的演算法是將陣列先分為n個陣列，進行排序，再講n/2個有序陣列進行排序，
//以此類推最后將最后0-mid,和mid+1~high這兩個有序陣列進行排序,時間復雜度為O(nlogn)
{
SimpleMergeSort(arr,0,len-1);
out_print(arr,len);
}*/
#include<iostream>
using namespace std;
void out_print(int arr[],int len);//輸出函式
void swap(int &i,int &j);//交換函式
void Straigthinsertsort(int arr[],int len);//直接插入排序
void ShellInsert(int arr[],int len,int incr);
void shellSort(int arr[],int len,int t,int inc);//希爾排序
int partition(int arr[],int low,int high);//快速排序
void quitsorthelp(int arr[],int low,int high);
void QuitSort(int arr[],int len);
void SimpleSelectSort(int arr[],int len);//簡單排序
void SiftAdjust(int arr[],int low,int high);//堆排序
void HeapSort(int arr[],int len);
void MergeSort(int arr[],int len);
int main()
{
int arr[]={12,4,5,64,6,23,7,34,19,10};
int len=sizeof(arr)/sizeof(int);
//Straigthinsertsort(arr,len);
/*int t=len/2;
int inc=t; //inc為增量，從len/2開始，每次減一，知道減為0，shell排序的基本思想，陣列越有序，時間復雜度越低，最低為O(n^1.5);
shellSort(arr,len,t,inc);*/
//QuitSort(arr,len);
//SimpleSelectSort(arr,len);
//HeapSort(arr,len);
MergeSort(arr,len);
return 0;
}
uj5u.com熱心網友回復：
樓主這是分享還是提問？uj5u.com熱心網友回復：
無私奉獻無私奉獻uj5u.com熱心網友回復：
樓主要干嘛？轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/94372.html
標籤：基礎類
上一篇：運行時問題：[BCC32 Error] strsvr.cpp(2): E2209 Unable to open include file 'vcl.h'
下一篇：c語言實作單鏈表生成