排序算法总结(C#版)

算法质量的衡量标准:

1:时间复杂度:分析关键字比较次数和记录的移动次数;

2:空间复杂度:需要的辅助内存;

3:稳定性:相同的关键字计算后,次序是否不变。


简单排序方法

1、直接插入排序

直接插入排序(InsertionSort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止

例如 int [] a=new int[]{42,20,17,27,13,8,48}

一般设数组为a[0…n-1]

1.     初始时,a[0]自成1个有序区,无序区为a[1..n-1]。令i=1

2.     a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。

3.     i++并重复第二步直到i==n-1。排序完成。

for循环 n-1次,插入数据,,跟前面的一个个比较。。

如果a[j]前一个数据a[j-1] > a[j],就交换a[j]a[j-1]j-- 直到a[j-1]<= a[j]。这样也可以实现将一个新数据新并入到有序区间。 

 //从小到大直接插入排序方法
        public static void InsertSort(SeqList<int> seqList)
        {
            for(int i = 1; i <=seqList.Last ; i++)   //Last+1个元素,插入 Last次就行
            {
               for (int j = i-1; j >=0 && seqList[j+1]<seqList [j]; j--) //如果[1]<[0],即插入的比原有的小,则交换,,
               {
                   int tmp = seqList[j];
                   seqList[j] = seqList[j + 1];
                   seqList[j+1] = tmp;
               }
            }
  }

2冒泡排序(小的数往前冒“排”)

1.比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交换。

2.这样对数组的第N-1个数据到0个数据进行一次遍历后,最小的一个数据就到数组第0个位置。

3.重复前面二步,

冒泡排序毕竟是一种效率低下的排序方法,在数据规模很小时,可以采用。数据规模比较大时,最好用其它排序方法。

 

//从小到大冒泡排序方法
        public static void BubbleSort(SeqList<int>seqList)
        {
            for(int i = 0; i < seqList.Last ; i++)  //last+1个数,循环last次,下标到last
            {
               for (int j=seqList.Last-1;j>=i ; j--)  //从右边排到左边,已经冒出的就不用比较了
               {
                   if (seqList[j+1] < seqList[j]) //后面的数小
                   {
                        int tmp = seqList[j];
                        seqList[j] = seqList[j+ 1];
                        seqList[j + 1] = tmp;
                   }
               }
            }
        }</span>

3、简单选择排序算法

 

思路:

第一次从R[0]~R[n-1]中选取最小值,与R[0]交换,第二次从R{1}~R[n-1]中选取最小值,与R[1]交换,...., 第i次从R[i-1]~R[n-1]中选取最小值,与R[i-1]交换,.....,第n-1次从R[n-2]~R[n-1]中选取最小值,与R[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列。

1、设数组内存放了n个待排数字,数组下标从1开始,到n结束。

2、初始化i=1

3、从数组的第i个元素开始到第n个元素,寻找最小的元素。

4、将上一步找到的最小元素和第i位元素交换

5i++,直到i=n1算法结束,否则回到第3

 

 //从小到大简单选择排序方法
        public static void SimpleSelectSort(SeqList<int>seqList)
        {
            for(int i = 0; i <seqList.Last; i++)  //循环n-1趟。第i趟,在i之后找最小的数与[i]交换
            {
               int minIndex=i;
               for (int j = i + 1; j <= seqList.Last; j++)  //从(i+1)开始找最小的数,因为前i个已经有序。
               {
                   if (seqList[j] <seqList[minIndex]) 
                        minIndex = j;                     //最小的是[j]
               }
               int tmp = seqList[i]; //3.与第i个记录交换
               seqList[i] = seqList[minIndex];
               seqList[minIndex] = tmp;
            }
        }
 

此3种排序算法的复杂度一样,最好情况下为O(n),最坏和平均情况下都是O(n^2),都是稳定的排序算法。

快速排序

对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

 

 //快速排序
        public static void QuickSort(SeqList<int> seqList,int low, int high)
        {
            int i = low;
            int j = high;
            int tmp = seqList[low];  //分界点
            while(low < high )
            {
               while ((low<high)&&(seqList[high ]>=tmp))//后边比tmp大的不动
               {
                   --high;
               }
               seqList[low] = seqList[high]; //将比tmp小的放在前面,low位置
 
               while ((low < high) &&(seqList[low] <= tmp))  //前面比tmp小的不动
               {
                   ++low ;
               }
               seqList [high ]=seqList [low ]; //将比tmp大的放在后面,high位置
                   //知道此时  low=high                                          
            }
           seqList[high] = seqList[low] = tmp;//此时low=high ,就完成了以tmp值来分界
 
            //分别对前后两部分来 快速排序
            if(i < low - 1)   //对tmp前面的数(0到low-1)递归调用,,此时【low】==tmp,low=high
            {
               QuickSort(seqList, i, low - 1);
            }
            if(low + 1 < j)   //对tmp后面的数(low+1到j)递归调用,,此时【low】==tmp,low=high
            {
               QuickSort(seqList, low + 1, j);
            }
        }</span>

堆排序

在程序设计相关领域,堆(Heap)的概念主要涉及到两个方面:

  • 一种数据结构,逻辑上是一颗完全二叉树,存储上是一个数组对象(二叉堆)
  • 垃圾收集存储区,是软件系统可以编程的内存区域。

本文所说的堆,指的是前者。

堆排序算法是基于完全二叉树的排序算法,把一颗完全二叉树调整为堆,时间复杂度是O(nlgN),与快速排序达到相同的时间复杂度。但是在实际应用中,我们往往采用快速排序而不是堆排序。这是因为快速排序的一个好的实现,往往比堆排序具有更好的表现。堆排序的主要用途,是在形成和处理优先级队列方面。另外,如果计算要求是类优先级队列(比如,只要返回最大或者最小元素,只有有限的插入要求等),堆同样是很适合的数据结构。

 

二叉堆的定义

二叉堆是完全二叉树或者是近似完全二叉树。

二叉堆满足二个特性:

1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。

2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆:


堆的存储

一般都用数组来表示堆,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。



  • 堆排序 HeapSort( A ):

    堆排序的过程是,设有n个记录,首先将这n个记录按关键码建成堆,将堆顶记录输出,得到n个记录中关键码最大(或最小)的记录。然后,把剩下的n-1个记录,输出堆顶记录,得到n个记录中关键码次大(或次小)的记录。如此反复,便可得到一个按关键码有序的序列。

    需解决两个问题:1、如何建堆,2、输出堆顶后,怎么样调整剩下的n-1个记录,使其按关键码成为一个新堆。

      

      堆排序算法的基本思想是,将数组A创建为一个最大堆,然后交换堆的根(最大元素)和最后一个叶节点x,将x从堆中去掉形成新的堆A1,然后重复以上动作,直到堆中只有一个节点。

归并排序

主要是二路归并排序,基本思想是:将两个有序表合并为一个有序表。(n个数为n个长度为1的表,合并为n/2个长度为2的表,以此类推,最终生成1个长度为n的表)

该算法是采用分治法Divide and Conquer  将大化小,将复杂归为简单)的一个非常典型的应用。

 

分治法的精髓:(是很多高效算法的基础,如排序算法(快速排序归并排序),傅立叶变换(快速傅立叶变换))
分--将问题分解为规模更小的子问题;
治--将这些规模更小的子问题逐个击破;
合--将已解决的子问题合并,最终得出“母”问题的解;

归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数列的过程,时间复杂度可以记为O(N),故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作,所以归并排序在O(N*logN)的几种排序方法(快速排序,归并排序,希尔排序,堆排序)也是效率比较高的。也是稳定的排序算法。

基数排序 

与前面的排序算法(通过关键码的比较和移动来排序)完全不同,基数排序是一种借助于多关键码排序的思想,是将单关键码按基数分成多关键码进行排序的方法,是一种分配排序。

基数排序只适合于字符串和整数这种有明显结构特征的关键码

它是怎么排序的呢?我们可以按照下面的一组数字做出说明:12、 104、 13、 7、 9

    (1)按个位数排序是12、13、104、7、9

    (2)再根据十位排序104、7、9、12、13

    (3)再根据百位排序7、9、12、13、104

    这里注意,如果在某一位的数字相同,那么排序结果要根据上一轮的数组确定,举个例子来说:07和09在十分位都是0,但是上一轮排序的时候09是排在07后面的;同样举一个例子,12和13在十分位都是1,但是由于上一轮12是排在13前面,所以在十分位排序的时候,12也要排在13前面。

    所以,一般来说,10基数排序的算法应该是这样的

    (1)判断数据在各位的大小,排列数据;

    (2)根据1的结果,判断数据在十分位的大小,排列数据。如果数据在这个位置的余数相同,那么数据之间的顺序根据上一轮的排列顺序确定;

    (3)依次类推,继续判断数据在百分位、千分位......上面的数据重新排序,直到所有的数据在某一分位上数据都为0。


各种排序算法的复杂度和稳定性

 


原文地址:https://www.cnblogs.com/peterYong/p/6556710.html