文章、图片参考:http://www.jianshu.com/p/1b4068ccd505?hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io
这里用C++实现了部分排序,待更新。。。
名词解释:
n: 数据规模
k:“桶”的个数
In-place: 占用常数内存,不占用额外内存
Out-place: 占用额外内存
稳定性:排序后2个相等键值的顺序和排序之前它们的顺序相同
冒泡排序动图演示:
选择排序动图演示:
插入排序动图演示:
归并排序动图演示:
快速排序动图演示:
堆排序动图演示:
计数排序动图演示:
LSD基数排序动图演示:
1 #include <bits/stdc++.h>
using namespace std;
void InsertSort(int na[],int n)
{
int tem,i,j;
for(i=; i<n; i++)
{
tem=na[i];
j=i-;
while(j>=&&tem<na[j])
{
na[j+]=na[j];
j--;
}
na[j+]=tem;
}
}
void ShellSort(int na[],int n)
{
int i,j,d,tem;
d=n/;
while(d>)
{
for(i=d; i<n; i++)
{
j=i-d;
while(j>=&&na[j]>na[j+d])
{
tem=na[j];
na[j]=na[j+d];
na[j+d]=tem;
j=j-d;
}
}
d=d/;
}
}
void BubbleSort(int na[],int n)
{
int i,j;
for(i=; i<n-; i++)
for(j=n-; j>i; j--)
if(na[j]<na[j-])
{
na[j] ^= na[j-];
na[j-] ^= na[j];
na[j] ^= na[j-];
}
}
void QuickSort(int na[],int s,int t)
{
int i=s,j=t,tem;
if(s<t)
{
tem=na[s];
while(i!=j)
{
while(j>i&&na[j]>tem)j--;
na[i]=na[j];
while(i<j&&na[i]<tem)i++;
na[j]=na[i];
}
na[i]=tem;
QuickSort(na,s,i-);
QuickSort(na,i+,t);
}
}
void SelectSOrt(int na[],int n)
{
int i,j,k;
for(i=; i<n-; i++)
{
k=i;
for(j=i+; j<n; j++)
if(na[j]<na[k])
k=j;
if(k!=i)
{
na[i] ^= na[k];
na[k] ^= na[i];
na[i] ^= na[k];
}
}
}
void Heap_Sift(int na[],int low,int high)
{
int i=low,j=*i;
int tem=na[i];
while(j<=high)
{
if(j<high&&na[j]<na[j+])j++;
if(tem<na[j])
{
na[i]=na[j];
i=j;
j=*i;
}
else break;
}
na[i]=tem;
}
void Heap_HeapSOrt(int na[],int n)
{
int i,j;
for(i=; i>=; i--)
na[i]=na[i-];
for(i=n/; i>=; i--)
Heap_Sift(na,i,n);
for(i=n; i>=; i--)
{
na[] ^= na[i];
na[i] ^= na[];
na[] ^= na[i];
Heap_Sift(na,,i-);
}
}
void Merge_Merge(int na[],int low,int mid,int high)
{
int *n1;
int i=low,j=mid+,k=;
n1=(int *)malloc((high-low+)*sizeof(int));
while(i<=mid&&j<=high)
if(na[i]<=na[j])
n1[k++]=na[i++];
else
n1[k++]=na[j++];
while(i<=mid)
n1[k++]=na[i++];
while(j<=high)
n1[k++]=na[j++];
for(k=,i=low; i<=high; k++,i++)
na[i]=n1[k];
}
void Merge_MergePass(int na[],int length,int n)
{
int i;
for(i=; i+*length-<n; i=i+*length)
Merge_Merge(na,i,i+length-,i+*length-);
if(i+length-<n)
Merge_Merge(na,i,i+length-,n-);
}
void Merge_MergeSort(int na[],int n)
{
int length,k,i=;
for(length=; length<n; length=*length)
Merge_MergePass(na,length,n);
}
void CountSort(int na[],int n)
{
int nmax=,i,j;
for(i=; i<n; i++)
nmax=max(nmax,na[i]);
int na1[nmax+]= {};
for(i=; i<n; i++)
na1[na[i]]++;
for(j=,i=; i<=nmax; i++)
while(na1[i]--)
na[j++]=i;
}
void Display(int na[],int n,string s)
{
cout<<s<<": ";
for(int i=; i<n; i++)
cout<<na[i]<<" ";
cout<<endl;
}
void Display(int na[],int n)
{
cout<<"HeapSort: ";
for(int i=; i<=n; i++)
cout<<na[i]<<" ";
cout<<endl;
}
#define n 10
int main()
{
int na[n]= {,,,-,,,,,,};
InsertSort(na,n);
Display(na,n,"InsertSort"); int na1[n]= {,,,,,,-,,,};
ShellSort(na1,n);
Display(na1,n,"ShellSort"); int na2[n]= {,,,,,,-,,,};
BubbleSort(na2,n);
Display(na2,n,"BubbleSort"); int na3[n]= {,,,,,,,-,,};
QuickSort(na3,,n-);
Display(na3,n,"QuickSort"); int na4[n]= {,,,,,,-,,,};
SelectSOrt(na4,n);
Display(na4,n,"SelectSort"); int na5[n]= {,,,,,,,,-,};
Heap_HeapSOrt(na5,n);
Display(na5,n); int na6[n]= {,,,,,-,-,,,};
Merge_MergeSort(na6,n);
Display(na6,n,"MergeSort"); int na7[n]= {,,,,,,,,,};
CountSort(na7,n);
Display(na7,n,"CountSort(don't sort minus)");
return ;
}