(C/C++学习)9.C/C++优化排序

说明： 常见的排序算法都是比较排序，非比较排序包括计数排序、桶排序和基数排序，非比较排序对数据有要求，因为数据本身包含了定位特征，所有才能不通过比较来确定元素的位置。比较排序的时间复杂度通常为O(n2)或者O(nlogn)，比较排序的时间复杂度下界就是O(nlogn)，而非比较排序的时间复杂度可以达到O(n)，但是都需要额外的空间开销。本文将介绍的是各种比较排序算法：

一. 各种排序算法的比较：

二. 未优化的冒泡选择排序法

1.选择排序法

 void sortlist1(int *arr,int n)

 {

     for(int i = 0;i < n-1;i++)

     {

         for(int j = i+1;j < n;j++)

         {

             if(arr[i] > arr[j])

             {

                 arr[i] ^= arr[j];

                 arr[j] ^= arr[i];

                 arr[i] ^= arr[j];

             }

         }

     }

 }

2.冒泡排序法

 void sortlist2(int *arr,int n)

 {

     for(int i = 0;i < n-1;i++)

     {

         for(int j = 0;j < n-1-i;j++)

         {

             if(arr[j] > arr[j+1])

             {

                 arr[j]   ^= arr[j+1];

                 arr[j+1] ^= arr[j];

                 arr[j]   ^= arr[j+1];

             }

         }

     }

 }

三.优化冒泡选择两种排序方法

1.选择排序法的优化（以从小到大的排列顺序为例）

从上面的代码可知，选择排序法的思想是让第 i（i 从0开始）个元素分别与其后面的每个元素进行比较，当比较结果为大于时，就进行交换，这样比较一轮下来，第i个元素成了此轮比较中的最小元素，再继续比较完所有轮，就实现了数组从小到大的排列。这样的排列使得选择排序法的交换次数过于多，降低了排序效率。所以，对选择排序法的优化方案就是：比而不换，记录下标！

 void sortlist(int *p,int n)

 {

     for(int i = 0;i<n;i++)

     {

         int idx = i;

         for(int j = i+1;j<n;j++)

         {

             if(p[idx] > p[j])

                 idx = j;

         }

         if(idx != i)

         {

             p[idx] ^= p[i];

             p[i] ^= p[idx];

             p[idx] ^= p[i];

         }

     }

 }

如上代码，每次内重循环之后，idx记录本次循环中比较的最小值或最大值（此处为最小值），若idx != i,则说明 i 并不是这次比较的最大或最小值,则进行交换，结束本次循环。

2.冒泡排序法优化（以从小到大为例）

冒泡排序法的思想是每轮用第 j（j从0开始）个元素与第 j+1个元素进行比较，如果大于则交换；这样一轮下来，最大的元素就像冒泡一样到了最后，这样继续比较完所有轮，就实现了冒泡从小到大排序。由此可见，对于冒泡排序法，当某一轮中没有发生过元素的交换时，则表明整个元素序列已经有序了，从而不需要在比较下去。因此，冒泡排序的优化方案为：序而不排。

 void sortlist2(int *p,int n)

 {

     for(int i = 0;i<n;i++)

     {

         int flag = 0;

         for(int j = 0;j<n-1-i;j++)

         {

             if(p[j] > p[j+1])

             {

                 p[j] ^= p[j+1];

                 p[j+1] ^= p[j];

                 p[j] ^= p[j+1];

                 flag = 1;

             }

         }

         if(flag == 0)

             break;

     }

 }

如果在一个内循环之内,都为有序排列,即没发生过交换事件，则标志flag为0，直接退出循环。

四. 快速排序

排序思想：对一组元素，选取第一个元素为比较基数，然后其他元素与他进行比较，比它大的放右边，比它小的放左边，一轮完成，该元素左边都是比它自身小的，右边都是比它大的；然后分别对刚才基数左边和右边的元素重复上述操作，直至排序完成。

 void sortlist3(int *p,int low,int high)

 {

     if(low < high)

         //判断元素是否大于1,至少2个元素才排序

         int l = low;

         int h = high;

         int middle = p[low ];

          //此处只能用p[low],不能用p[0],因为后面递归要用到

         while(l < h)

         {

             while(p[h] >= middle && l<h)

                 h--;

             p[l] = p[h];

             while(p[l] <= middle && l<h)

                 l++;

             p[h] = p[l];

         }

         p[h] = middle;

         sortlist3(p,low,h-1);

         sortlist3(p,h+1,high);

     }

 }

其中 p 为数组名，low为数组起始地址 0，high 为数组的元素个数减1。

五.插入排序法

 void insertsort(int arr[],int length,int beg = ,int step = ) {

     for(int i = beg+step; i<length; i+=step) {

         if(arr[i] < arr[i-step]) {

             int temparr = arr[i];

             int temp = i;

             while(temp-step>=beg && temparr<arr[temp-step]) {

                 arr[temp] = arr[temp-step];

                 temp = temp - step;

             }

             arr[temp] = temparr;

         }

     }

 }

六.希尔排序法

 void shellsort(int arr[],int length) {

     cout<<"Shellsort the array:      ";

     int increment = length/+;

     int flag = ;

     while(increment>=) {

         if(increment == )

             flag = ;

         for(int i = ; i<increment; i+=increment)

             insertsort(arr,length,i,increment);          //插入排序

         if(flag == )

             break;

         increment = increment/+;

     }

 }

七. 归并排序法

 /*合并两个有序数组*/

 void unionarray(int arr[],int beg,int mid,int end,int*p) {

     int temp = mid+;

     int begg = beg;

     for(int i = ;i<end-beg+;i++) {

         if(begg > mid)

             p[i] = arr[temp++];

         else if(temp>end)

             p[i] = arr[begg++];

         else {

             if(arr[begg]>arr[temp])

                 p[i] = arr[temp++];

             else

                 p[i] = arr[begg++];

         }

     }

     for(int i = beg;i<=end;i++)

         arr[i] = p[i-beg];

 }

 /*归并排序*/

 void GuiBingsort(int arr[],int beg,int end,int *p) {

     if(beg >= end)

         return ;

     int mid = (beg+end)/;

     GuiBingsort(arr,beg,mid,p);

     GuiBingsort(arr,mid+,end,p);

     unionarray(arr,beg,mid,end,p);

 }

八. 堆排序

 /*交换数组两个元素*/

 void swap(int arr[],int a,int b) {

     int temp = arr[a];

     arr[a] = arr[b];

     arr[b] = temp;

 }

 /*大顶堆维护*/

 void heapAdjust(int arr[],int pos,int _size) {

     int max = pos;

     int lchild = pos*+;

     int rchild = pos*+;

     if(lchild<_size && arr[lchild]>arr[max])

         max = lchild;

     if(rchild<_size && arr[rchild]>arr[max])

         max = rchild;

     if(pos != max) {

         swap(arr,pos,max);

         heapAdjust(arr,max,_size);

     }

 }

 /*堆排序主程序*/

 void heapsort(int arr[],int _size) {

     for(int i = _size/-;i>=;i--)

         heapAdjust(arr,i,_size);

     for(int i = _size-;i>;i--) {

         swap(arr,i,);

         heapAdjust(arr,,i);

     }

 }

巴特西

(C/C++学习)9.C/C++优化排序

最新文章

热门文章