第七轮过后状态如下(已经是有序了,所以没有改变):

一.常见排序算法的实现

简介

排序算法是我们编程中遇到的最多的算法。目前主流的算法有8种。

  平均时间复杂度从高到低依次是:

    
冒泡排序(o(n2)),选择排序(o(n2)),插入排序(o(n2)),堆排序(o(nlogn)),

     归并排序(o(nlogn)),快速排序(o(nlogn)),
希尔排序(o(n1.25)),基数排序(o(n))

这些平均时间复杂度是参照维基百科排序算法罗列的。

是计算的理论平均值,并不意味着你的代码实现能达到这样的程度。

例如希尔排序,时间复杂度是由选择的步长决定的。基数排序时间复杂度最小,

但我实现的基数排序的速度并不是最快的,后面的结果测试图可以看到。

本文代码实现使用的数据源类型为IList<int>,这样可以兼容int[]和List<int>(虽然int[]有ToList(),

List<int>有ToArray(),哈哈!)。

继续让8和7比较,发现8比7要大,所以8和7交换位置。

 

二分查找法优化插入排序

插入排序主要工作是在有序的数列中对要排序的数查找合适的位置,而查找里面经典的二分查找法正可以适用。

原理:通过二分查找法的方式找到一个位置索引。当要排序的数插入这个位置时,大于前一个数,小于后一个数。

实现如下:

public static void InsertSortImprovedWithBinarySearch(IList<int> data)
        {
            int temp;
            int tempIndex;
            for (int i = 1; i < data.Count; i++)
            {
                temp = data[i];
                tempIndex = BinarySearchForInsertSort(data, 0, i, i);
                for (int j = i - 1; j >= tempIndex; j--)
                {
                    data[j + 1] = data[j];
                }
                data[tempIndex] = temp;
            }
        }

        public static int BinarySearchForInsertSort(IList<int> data, int low, int high, int key)
        {
            if (low >= data.Count - 1)
                return data.Count - 1;
            if (high <= 0)
                return 0;
            int mid = (low + high) / 2;
            if (mid == key) return mid;
            if (data[key] > data[mid])
            {
                if (data[key] < data[mid + 1])
                    return mid + 1;
                return BinarySearchForInsertSort(data, mid + 1, high, key);
            }
            else  // data[key] <= data[mid]
            {
                if (mid - 1 < 0) return 0;
                if (data[key] > data[mid - 1])
                    return mid;
                return BinarySearchForInsertSort(data, low, mid - 1, key);
            }
        }

过程解析:需要注意的是二分查找方法实现中high-low==1的时候mid==low,所以需要33行

mid-1<0即mid==0的判断,否则下行会索引越界。

冒泡排序第三版

3 堆排序(HeapSort)

针对这个版本的缺点,我进行了优化

实现如下:

public static void QuickSortRelaxImproved(IList<int> data)
        {
            QuickSortRelaxImproved(data, 0, data.Count - 1);
        }

        public static void QuickSortRelaxImproved(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[(low + high) / 2];
            int i = low - 1, j = high + 1;
            int index = (low + high) / 2;
            while (true)
            {
                while (data[++i] < temp) ;
                while (data[--j] > temp) ;
                if (i >= j) break;
                Swap(data, i, j);
                if (i == index) index = j;
                else if (j == index) index = i;
            }
            if (j == i)
            {
                QuickSortRelaxImproved(data, j + 1, high);
                QuickSortRelaxImproved(data, low, i - 1);
            }
            else //i-j==1
            {
                if (index >= i)
                {
                    if (index != i)
                        Swap(data, index, i);
                    QuickSortRelaxImproved(data, i + 1, high);
                    QuickSortRelaxImproved(data, low, i - 1);
                }
                else //index < i
                {
                    if (index != j)
                        Swap(data, index, j);
                    QuickSortRelaxImproved(data, j + 1, high);
                    QuickSortRelaxImproved(data, low, j - 1);
                }
            }
        }

public static void QuickSortRelaxImproved(IList<int> data)
        {
            QuickSortRelaxImproved(data, 0, data.Count - 1);
        }

        public static void QuickSortRelaxImproved(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[(low + high) / 2];
            int i = low - 1, j = high + 1;
            int index = (low + high) / 2;
            while (true)
            {
                while (data[++i] < temp) ;
                while (data[--j] > temp) ;
                if (i >= j) break;
                Swap(data, i, j);
                if (i == index) index = j;
                else if (j == index) index = i;
            }
            if (j == i)
            {
                QuickSortRelaxImproved(data, j + 1, high);
                QuickSortRelaxImproved(data, low, i - 1);
            }
            else //i-j==1
            {
                if (index >= i)
                {
                    if (index != i)
                        Swap(data, index, i);
                    QuickSortRelaxImproved(data, i + 1, high);
                    QuickSortRelaxImproved(data, low, i - 1);
                }
                else //index < i
                {
                    if (index != j)
                        Swap(data, index, j);
                    QuickSortRelaxImproved(data, j + 1, high);
                    QuickSortRelaxImproved(data, low, j - 1);
                }
            }
        }

过程解析:定义了一个变量Index,来跟踪哨兵的位置。发现哨兵最后在小于自己的那堆,

那就与j交换,否则与i交换。达到每次递归都能减少要排序的数列数总和的目的。

图片 1

以上动图由“图斗罗”提供

图片 2

1 快速排序(QuickSort)

鸡尾酒排序(来回排序)

图片 3

  • 第一趟比较前两个数,然后把第二个数按大小插入到有序表中;

图片 4

首先让5和8比较,发现5比8要小,因此元素位置不变。

                   (
按照算法的第三步从后面开始找

选择排序

选择排序是我觉得最简单暴力的排序方式了。

以前刚接触排序算法的时候,感觉算法太多搞不清,唯独记得选择排序的做法及实现。

原理:找出参与排序的数组最大值,放到末尾(或找到最小值放到开头) 维基入口

实现如下:

public static void SelectSort(IList<int> data)
        {
            for (int i = 0; i < data.Count - 1; i++)
            {
                int min = i;
                int temp = data[i];
                for (int j = i + 1; j < data.Count; j++)
                {
                    if (data[j] < temp)
                    {
                        min = j;
                        temp = data[j];
                    }
                }
                if (min != i)
                    Swap(data, min, i);
            }
        }

过程解析:将剩余数组的最小数交换到开头。

而我们的冒泡排序之所以叫做冒泡排序,正是因为这种排序算法的每一个元素都可以像小气泡一样,根据自身大小,一点一点向着数组的一侧移动。

void InsertSortArray()
{
    for(int i=1;i<n;i++)//循环从第二个数组元素开始,因为arr[0]作为最初已排序部分
    {
        int temp=arr[i];//temp标记为未排序第一个元素
        int j=i-1;
        while (j>=0 && arr[j]>temp)/*将temp与已排序元素从大到小比较,寻找temp应插入的位置*/
        {
            arr[j+1]=arr[j]; 
            j--;
        }
        arr[j+1]=temp;
    }
} 

对冒泡排序进行更大的优化

冒泡排序只是单向冒泡,而鸡尾酒来回反复双向冒泡。

原理:自左向右将大数冒到末尾,然后将剩余数列再自右向左将小数冒到开头,如此循环往复。维基入口

实现如下:

public static void BubbleCocktailSort(IList<int> data)
        {
            bool flag;
            int m = 0, n = 0;
            for (int i = data.Count - 1; i > 0; i--)
            {
                flag = true;
                if (i % 2 == 0)
                {
                    for (int j = n; j < data.Count - 1 - m; j++)
                    {
                        if (data[j] > data[j + 1])
                        {
                            Swap(data, j, j + 1);
                            flag = false;
                        }
                    }
                    if (flag) break;
                    m++;
                }
                else
                {
                    for (int k = data.Count - 1 - m; k > n; k--)
                    {
                        if (data[k] < data[k - 1])
                        {
                            Swap(data, k, k - 1);
                            flag = false;
                        }
                    }
                    if (flag) break;
                    n++;
                }
            }
        }

过程解析:分析第i轮冒泡,i是偶数则将剩余数列最大值向右冒泡至末尾,是奇数则将剩余数列最小值

向左冒泡至开头。对于剩余数列,n为始,data.Count-1-m为末。

来回冒泡比单向冒泡:对于随机数列,更容易得到有序的剩余数列。因此这里使用标识将会提升的更加明显。

图片 5

  • 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;

  • 依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。

通过标识提升冒泡排序

在维基上看到,可以通过添加标识来分辨剩余的数是否已经有序来减少比较次数。感觉很有意思,可以试试。

实现如下:

public static void BubbleSortImprovedWithFlag(IList<int> data)
        {
            bool flag;
            for (int i = data.Count - 1; i > 0; i--)
            {
                flag = true;
                for (int j = 0; j < i; j++)
                {
                    if (data[j] > data[j + 1])
                    {
                        Swap(data, j, j + 1);
                        flag = false;
                    }
                }
                if (flag) break;
            }
        }

过程解析:发现某轮冒泡没有任何数进行交换(即已经有序),就跳出排序。

我起初也以为这个方法是应该有不错效果的,可是实际测试结果并不如想的那样。和未优化耗费时间一样(对于随机数列)。

由果推因,那么应该是冒泡排序对于随机数列,当剩余数列有序的时候,也没几个数要排列了!?

不过如果已经是有序数列或者部分有序的话,这个冒泡方法将会提升很大速度。

第一轮结束,数列有序区包含一个元素:

 

插入排序

插入排序是一种对于有序数列高效的排序。非常聪明的排序。只是对于随机数列,效率一般,交换的频率高。

原理:通过构建有序数列,将未排序的数从后向前比较,找到合适位置并插入。维基入口

第一个数当作有序数列。

实现如下:

public static void InsertSort(IList<int> data)
        {
            int temp;
            for (int i = 1; i < data.Count; i++)
            {
                temp = data[i];
                for (int j = i - 1; j >= 0; j--)
                {
                    if (data[j] > temp)
                    {
                        data[j + 1] = data[j];
                        if (j == 0)
                        {
                            data[0] = temp;
                            break;
                        }
                    }
                    else
                    {
                        data[j + 1] = temp;
                        break;
                    }
                }
            }
        }

过程解析:将要排序的数(索引为i)存储起来,向前查找合适位置j+1,将i-1到j+1的元素依次向后

移动一位,空出j+1,然后将之前存储的值放在这个位置。

这个方法写的不如维基上的简洁清晰,由于合适位置是j+1所以多出了对j==0的判断,但实际效率影响无差别。

建议比照维基和我写的排序,自行选择。

冒泡排序第二版

名称 复杂度 说明 备注
冒泡排序 BubbleSort O(N*N)

将待排序的元素看作是竖着排列的 “ 气泡 ” ,较小的元素比较轻,从而要往上浮

插入排序 InsertionSort O(N*N) 逐一取出元素,在已经排序的元素序列中从后向前扫描,放到适当的位置 起初,已经排序的元素序列为空
选择排序 SelcetionSort O(N*N) 首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此递归。
快速排序 QuickSort O(n*log2 (n)) 先选择中间值,然后把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使用这个过程(递归)。
堆排序 HeapSort O(n*log2 (n))

利用堆( heaps )这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构,并同时满足堆属性:即子节点的键值或索引总是小于(或者大于)它的父节点。

近似完全二叉树
希尔排序 ShellSort

O(n1+ )  0< £ <1

选择一个步长 (Step) , 然后按间隔为步长的单元进行排序 . 递归 , 步长逐渐变小 , 直至为 1.

箱排序 BinSort O(n)

设置若干个箱子,把关键字等于   k   的记录全都装入到第   k   个箱子里   (   分配   )   ,然后按序号依次将各非空的箱子首尾连接起来   (   收集   )   。

分配排序的一种:通过   "   分配   "   和   "   收集   "   过程来实现排序。

桶排序 BucketSort O(n)

桶排序的思想是把   [0   ,   1)   划分为   n   个大小相同的子区间,每一子区间是一个桶。

分配排序的一种:通过   "   分配   "   和   "   收集   "   过程来实现排序。

快速排序

快速排序是一种有效比较较多的高效排序。它包含了“分而治之”以及“哨兵”的思想。

原理:从数列中挑选一个数作为“哨兵”,使比它小的放在它的左侧,比它大的放在它的右侧。将要排序是数列递归地分割到

最小数列,每次都让分割出的数列符合“哨兵”的规则,自然就将数列变得有序。 维基入口

实现如下:

public static void QuickSortStrict(IList<int> data)
        {
            QuickSortStrict(data, 0, data.Count - 1);
        }

        public static void QuickSortStrict(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[low];
            int i = low + 1, j = high;
            while (true)
            {
                while (data[j] > temp) j--;
                while (data[i] < temp && i < j) i++;
                if (i >= j) break;
                Swap(data, i, j);
                i++; j--;
            }
            if (j != low)
                Swap(data, low, j);
            QuickSortStrict(data, j + 1, high);
            QuickSortStrict(data, low, j - 1);
        }

过程解析:取的哨兵是数列的第一个值,然后从第二个和末尾同时查找,左侧要显示的是小于哨兵的值,

所以要找到不小于的i,右侧要显示的是大于哨兵的值,所以要找到不大于的j。将找到的i和j的数交换,

这样可以减少交换次数。i>=j时,数列全部查找了一遍,而不符合条件j必然是在小的那一边,而哨兵

是第一个数,位置本应是小于自己的数。所以将哨兵与j交换,使符合“哨兵”的规则。

这个版本的缺点在于如果是有序数列排序的话,递归次数会很可怕的。

按照现有的逻辑,有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1,第二轮排序过后的有序区长度是2
……

                  (
按照算法的第四步从前面开始找>X的值,65>49,两者交换,此时I:=3
)

另一个版本

这是维基上的一个C#版本,我觉得很有意思。这个版本并没有严格符合“哨兵”的规则。但却将“分而治之”

以及“哨兵”思想融入其中,代码简洁。

实现如下:

public static void QuickSortRelax(IList<int> data)
        {
            QuickSortRelax(data, 0, data.Count - 1);
        }

        public static void QuickSortRelax(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[(low + high) / 2];
            int i = low - 1, j = high + 1;
            while (true)
            {
                while (data[++i] < temp) ;
                while (data[--j] > temp) ;
                if (i >= j) break;
                Swap(data, i, j);
            }
            QuickSortRelax(data, j + 1, high);
            QuickSortRelax(data, low, i - 1);
        }

过程解析:取的哨兵是数列中间的数。将数列分成两波,左侧小于等于哨兵,右侧大于等于哨兵。

也就是说,哨兵不一定处于两波数的中间。虽然哨兵不在中间,但不妨碍“哨兵”的思想的实现。所以

这个实现也可以达到快速排序的效果。但却造成了每次递归完成,要排序的数列数总和没有减少(除非i==j)。

至于后续的交换细节,我们这里就不详细描述了,第三轮过后的状态如下:

Shell排序比冒泡排序快5倍,比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相对比较简单,它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。

冒泡排序

冒泡排序是笔试面试经常考的内容,虽然它是这些算法里排序速度最慢的(汗),后面有测试为证。

原理:从头开始,每一个元素和它的下一个元素比较,如果它大,就将它与比较的元素交换,否则不动。

这意味着,大的元素总是在向后慢慢移动直到遇到比它更大的元素。所以每一轮交换完成都能将最大值

冒到最后。  维基入口

实现如下:

public static void BubbleSort(IList<int> data)
        {
            for (int i = data.Count - 1; i > 0; i--)
            {
                for (int j = 0; j < i; j++)
                {
                    if (data[j] > data[j + 1])
                        Swap(data, j, j + 1);
                }
            }
        }

过程解析:中需要注意的是j<i,每轮冒完泡必然会将最大值排到数组末尾,所以需要排序的数应该是在减少的。

很多网上版本每轮冒完泡后依然还是将所有的数进行第二轮冒泡即j<data.Count-1,这样会增加比较次数。

这样一来,元素9作为数列的最大元素,就像是汽水里的小气泡一样漂啊漂,漂到了最右侧。

7 交换排序(ExchangeSort)和选择排序(SelectSort)

图片 6

进行第一次交换后:   27        38      
65       97       76       13        49

下面,让我们来进行第二轮排序:

直接插入排序(straight insertion
sort)的作法是:

图片 7

 
详细分析:见快速排序。

元素3和1比较,发现3大于1,所以3和1交换。

一趟快速排序的算法是:

实际上,数列真正的有序区可能会大于这个长度,比如例子中仅仅第二轮,后面5个元素实际都已经属于有序区。因此后面的许多次元素比较是没有意义的。

按照定义很容易写出代码:

元素6和7比较,发现6小于7,所以位置不变。

这两种排序方法都是交换方法的排序算法,效率都是
O(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段,在实际中使用较少。

接下来让9和2比较,发现9比2要大,所以9和2交换位置。

冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素,使较大的数据下沉,较小的数据上升。它是O(n^2)的算法。

这个问题的关键点在哪里呢?关键在于对数列有序区的界定。

  
2)以第一个数组元素作为关键数据,赋值给X,即X:=A[1];

第二轮排序结束后,我们数列右侧的有序区有了两个元素,顺序如下:

冒泡排序是非常容易理解和实现,,以从小到大排序举例:

图片 8

9 总结
下面是一个总的表格,大致总结了我们常见的所有的排序算法的特点。

图片 9

进行第二次交换后:   27        38      
49       97       76       13        65

元素5和6比较,发现5小于6,所以位置不变。

 

图片 10

堆排序适合于数据量非常大的场合(百万数据)。

图片 11

5 插入排序(InsertSort)

接下来让8和6比较,发现8比6要大,所以8和6交换位置。

3.N=N-1,如果N不为0就重复前面二步,否则排序完成。

图片 12

void bubbleSort(int arr[],int n)
{
    int i,j,t;
     for(i=0;i<n-1;i++)
        for(j=0;j<n-i-1;j++)
            if(arr[j+1]<arr[j])
            {
              t=arr[j+1];
              arr[j+1]=arr[j];
              arr[j]=t;
             }
}

图片 13

 

元素3和2比较,发现3大于2,所以3和2交换。

  
4)、从I开始向后搜索,即由前开始向后搜索(I:=I+1),找到第一个大于X的值,两者交换;

元素7和8比较,发现7小于8,所以位置不变。

 详细分析:见冒泡排序。

接下来让9和1比较,发现9比1要大,所以9和1交换位置。

1.冒泡排序

具体如何来移动呢?让我们来看一个栗子:

8 基数排序(RadixSort)

图片 14

   5)、重复第3、4步,直到I=J;

接下来让6和3比较,发现6比3要大,所以6和3交换位置。

排序法 平均时间 最差情形 稳定度 额外空间 备注
冒泡 O(n2)     O(n2) 稳定 O(1) n小时较好
交换     O(n2)     O(n2) 不稳定 O(1) n小时较好
选择 O(n2) O(n2) 不稳定 O(1) n小时较好
插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好
基数 O(logRB) O(logRB) 稳定 O(n)

B是真数(0-9),

R是基数(个十百)

Shell O(nlogn) O(ns) 1<s<2 不稳定 O(1) s是所选分组
快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好
归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好
O(nlogn) O(nlogn) 不稳定 O(1) n大时较好

这一版代码中,sortBorder就是无序数列的边界。每一轮排序过程中,sortBorder之后的元素就完全不需要比较了,肯定是有序的。

堆排序会将所有的数据建成一个堆,最大的数据在堆顶,然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆,交换数据,依次下去,就可以排序所有的数据。

什么是冒泡排序?

6 冒泡排序(BubbleSort)

第八轮过后状态如下:

    
每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。

图片 15

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

图片 16

进行第三次交换后:   27        38      
13       97       76       49        65

图片 17

(
按照算法的第四步从前面开始找大于X的值,97>49,两者交换,此时J:=4
)

有8个数组成一个无序数列:5,8,6,3,9,2,1,7,希望从小到大排序。

4 Shell排序(ShellSort)
Shell排序通过将数据分成不同的组,先对每一组进行排序,然后再对所有的元素进行一次插入排序,以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。

图片 18

插入排序通过把序列中的值插入一个已经排序好的序列中,直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序,或者重复排序超过200数据项的序列。

元素4和5比较,发现4小于5,所以位置不变。

(1) 如果不多于1个数据,直接返回。
(2) 一般选择序列最左边的值作为支点数据。
(3)
将序列分成2部分,一部分都大于支点数据,另外一部分都小于支点数据。
(4) 对两边利用递归排序数列。

发表评论

电子邮件地址不会被公开。 必填项已用*标注