Sort 整理

文章、图片参考：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 ;

 }

巴特西

Sort 整理

冒泡排序动图演示：

选择排序动图演示：

插入排序动图演示：

归并排序动图演示：

快速排序动图演示：

堆排序动图演示：

计数排序动图演示：

LSD基数排序动图演示：

最新文章

热门文章