• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    6年前 (2013-04-15)  算法/数据结构 |   1 条评论  8 
    文章评分 0 次,平均分 0.0

    (1)排序算法的稳定性:所谓“稳定性”是指,在待排序数组出现的两个相同的元素,排序之后相对维持保持不变。比如:待排序数组为arr[] = {1,4,3,1},排序之后元素变为arr_new[] = {1,1,4,3},并且arr_new中的第一个是arr中的第一个1,arr_new中的第二个1是arr中的第二个1,这是我们就说这种排序时稳定的。sort

    (2)原地排序:所谓原地排序是指,不申请多余的空间来辅助完成排序算法,而是在原来的待排序的数据之上直接进行比较,交换,移动等操作。


    1.插入排序

    算法原理:将待排序的数组分为:有序区 和 无序区。然后每次从无序区取出第一个数据插入到有序区的正确位置,最终完成排序。

    算法代码:

     #include <iostream>
     
     using namespace std;
     
     void insert_sort(int *arr,int n)
     {
         int i,j;
         for(i = 1 ; i < n ; ++i)
         {
             int tmp = arr[i];
             j = i - 1;
             while( j >= 0 && arr[j] > tmp)
             {
                 arr[j+1] = arr[j];
                 j--;
             }
             arr[j+1]  = tmp;
         }
     }
     
     int main()
     {
         int arr[] = {2,4,1,3,5,8,7,6,8};
         insert_sort(arr,9);
         for(int i = 0  ; i < 9 ; ++i)
         {
             cout<<arr[i]<<" ";
         }
         cout<<endl;
         return 0;
     }

    小结:看代码可以知道这种排序算法的时间复杂度是O(n^2),并且插入排序时稳定的,属于原地排序。那么什么时候使用插入排序比较好呢?那就是当数组中的大部分数据已经有序时,使用插入排序算法的效率比较高,这种情况下,所需要进行的数据移动较少,而数据移动正式插入排序算法的主要步骤~~~~

    2.冒泡排序
    算法原理:冒泡排序是经过n-1趟子排序完成的,第 i 趟子排序从第1个数至第 n-i+1 个数,若第 i 个数比第 i+1 个数大,则交换这两个数,实际上这样经过 i 次子排序就使得 第1个数至第 n-i +1个数之间最大的数交换到了n-i+1 的位置上了。实际上冒泡排序时可以优化的,那就是当第 i 次子排序并没有发生元素的交换时,就说明数组已经排好序了,以后的子排序就不用做了。
    算法代码:

    #include <iostream>
     
     using namespace std;
     
     void swap(int &x,int &y)
     {
         x = x^y;
         y = x^y;
         x = x^y;
     }
     
     void bubble_sort(int *arr,int n)
     {
         int i,j;
         for(i = n - 1 ; i > 0 ; --i)
         {
             bool flag = true;
             for(j = 0 ; j < i ; ++j)
             {
                 if(arr[j] > arr[j+1])
                 {
                     flag = false;
                     swap(arr[j],arr[j+1]);
                 }
             }
             if(flag) //数组已经排好序没必要在继续进行其他子排序了
                 break;
         }
     }
     
     int main()
     {
         int arr[] = {2,1,4,3,8,7,5,6};
         bubble_sort(arr,8);
         for(int i = 0 ; i < 8 ; ++i)
         {
             cout<<arr[i]<<" ";
         }
         cout<<endl;
         return 0;
     }

    小结:冒泡排序算法的时间复杂度是O(n^2),同时冒泡排序也是稳定的,并且属于原地排序,排序的效率取决于逆序对的多少。采用一点小优化也加速了冒泡排序。

    3.选择排序
    算法原理:所谓选择排序经过 n-1 次选择,当进行第 i 次选择时,是从第1个元素到第 n-i+1 的元素中选择最大的元素和第 n-i+1 个位置的元素交换,这样做比如第1 次选择使得最大的元素到了数组的最后一个位置。注意哦,在选择排序中每次选择时只进行一次数据的交换。
    算法代码:

    #include <iostream>
     
     using namespace std;
     
     void swap(int &x,int &y)
     {
         int tmp = x;
         x = y;
         y = tmp;
     }
     
     void select_sort(int *arr,int n)
     {
         int i,j;
         for(i = n-1 ; i > 0 ; --i)
         {
             int tmp = 0;
             for(j = 1 ; j <= i ; ++j)
             {
                 if(arr[j] >= arr[tmp])//这里的“=”是保证选择排序稳定的关键
                 {
                     tmp = j;
                 }
             }
             swap(arr[i],arr[tmp]);
         }
     }
     int main()
     {
         int arr[] = {2,1,4,3,8,7,5,6};
         select_sort(arr,8);
         for(int i = 0 ; i < 8 ; ++i)
         {
             cout<<arr[i]<<" ";
         }
         cout<<endl;
         return 0;
     }

    小结:选择排序的思路非常的简单,实现起来也不难。时间复杂度是O(n^2),选择排序也是稳定的排序,并且也是原地排序。选择排序的时间基本不受数据的影响,因为不管怎样都要进行n-1次选择排序。

    4.归并排序
    算法原理:归并排序的思想是分治,将一个带排序的数组分成两个较小的数组,然后分别进行排序,组后将两个排好序的较小的数组合并起来,就得到了原来数组的排序后的结果。应该注意的是这种将两个排好序的数组合并有一个较好的算法,时间复杂度是O(n1+n2)的。n1、n2分别是两个小数组的长度。
    算法代码:

    #include <iostream>
     
     using namespace std;
     
     void merge_sort(int *arr,int start,int end,int *temp)
     {
         if(end > start+1)
         {
             int mid = start + (end - start) / 2;
             merge_sort(arr,start,mid,temp);
             merge_sort(arr,mid,end,temp);
             int i = start , j = mid , k = start;
             while(i < mid || j < end)
             {
                 if(j >= end || (i < mid && arr[i] <= arr[j]))
                 {
                     temp[k++] = arr[i++];
                 }
                 else
                 {
                     temp[k++] = arr[j++];
                 }
             }
             for(i = start ; i < end ; ++i)
             {
                 arr[i] = temp[i];
             }
         }
     }
     
     
     int main()
     {
         int temp[8];
         int arr[]  = {2,1,4,3,8,7,5,6};
         merge_sort(arr,0,8,temp);
         for(int i = 0 ; i < 8 ; ++i)
         {
             cout<<arr[i]<<" ";
         }
         cout<<endl;
         return 0;
     }

    小结:归并排序时稳定的排序,但是不属于原地排序,因为用了额外的O(n)的空间,时间复杂度降到了O(n*log n),并且对任意的数组进行排序时间复杂度都能控制在O(n*logn)。

    5.堆排序
    算法原理:所谓的堆排序是利用完全二叉树的思想实现的。首先应该提到的是最大堆,在最大堆中(完全二叉树二叉树)中每个父节点都大于等于两个儿子节点的值,这时候很明显堆顶是元素的最大值,然后把堆顶元素和堆中最后一个元素(分层遍历的节点编号最大的元素)交换,这样最大值就落到了数组的arr[n-1]的位置,然后把前n-1元素继续按照上面的方式处理,如此进行n-1次就完成堆排序。
    算法代码:

    #include <iostream>
     
     using namespace std;
     
     void swap(int &x,int &y)
     {
         x =  x + y;
         y =  x - y;
         x =  x - y;
     }
     
     void restore(int *arr,int s,int e)
     {
         int i = s , m;
         while(i <= e/2)
         {
             if(2*i+1 <= e && arr[2*i] > arr[2*i-1])
             {
                 m = 2 * i + 1;
             }
             else
             {
                 m = 2 * i;
             }
             if(arr[i-1] < arr[m-1])
             {
                 swap(arr[i-1],arr[m-1]);
                 i = m;
             }
             else
             {
                 i = e;
             }
         }
     }
     void heap_sort(int *arr,int n)
     {
         int i;
         for(i = n / 2 ; i > 0 ; --i)
         {    
             restore(arr,i,n);
         }
         for(i = n ; i > 1 ; --i)
         {
             swap(arr[0],arr[i-1]);
             restore(arr,1,i-1);
         }
     }
     
     int main()
     {
         int arr[] = {2,1,4,3,8,7,5,6};
         heap_sort(arr,8);
         for(int i = 0 ; i < 8 ; ++i)
         {
             cout<<arr[i]<<" ";
         }
         cout<<endl;
         return 0;
     }

    小结:堆排序是不稳定的排序,但是堆排序属于原地排序。时间复杂度是O(n*log n),并且不需要额外的辅助空间,也就是说堆排序是一种不错的排序算法哦~~~

    6.快速排序
    算法原理:快速排序时这样的一种排序,选取数组中的第一个元素arr[0]作为依据,遍历一遍数组后,使得数组中的第一个元素进入正确的位置,即在该位置左面的元素均小于等于arr[0],在该位置右面的元素均大于等于arr[0]。然后,在对该位置左面和右面的元素分别进行快速排序,如此一来完成整个数组的排序。
    算法代码:

    #include
    
     using namespace std;
    
     void swap(int &x,int &y)
     {
         x = x + y;
         y = x - y;
         x = x - y;
     }
    
     void quick_sort(int *arr,int s,int e)
     {
         if(s+1 < e)
         {
             int tmp = arr[s];
             int i = s+1;
             int j = e-1;
             while(i < j)
             {
                 while(i <= j && arr[i] <= tmp)
                 {
                     i++;
                 }
                 while(i <= j && arr[j] > tmp)
                 {
                     j--;
                 }
                 if(i < j)
                 {
                     swap(arr[i],arr[j]);
                 }
             }
             if(s != i-1)
                 swap(arr[s],arr[i-1]);
             quick_sort(arr,s,i-1);
             quick_sort(arr,i,e);
         }
     }
    
     int main()
     {
         int arr[] = {2,1,4,3,8,7,5,6};
         quick_sort(arr,0,8);
         for(int i = 0 ; i < 8 ; ++i)
         {
             cout<<arr[i]<<" ";
         }
         cout<<endl;
         return 0;
     }

    小结:首先还是说明快速排序时不稳定的,但是是原地排序,不需要额外的空间,时间复杂度是O(nlog n),实际上,这种把第一个元素作为依据元素只是快速排序的一种,STL中的sort内部实现是根据排序到了不同的阶段选用不同的排序算法。当数据量大是采用quick_sort排序,当分段递归到了数据量小于某个数值时,为避免quick_sort的递归调用带来的额外开销,就改用insert_sort 了;如果递归层次过深,还会考虑使用heap_sort 。

     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/679.html

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享