排序算法（内部排序）总结

排序是计算机应用中的一个非常重要的操作。平常我们总会听到一些算法，但是我们总是似懂非懂的写着代码，今天我将一般常见的排序算法进行一个总结。

本次总结只涉及内部排序（所谓内部排序是指在内存中进行的排序）

首先说一个概念:稳定排序与非稳定排序

如果一个序列中原来相同的元素，排序完成后，仍然保持着原来的顺序，那么就成为稳定排序，反之就是非稳定排序。

  　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　插入排序

     （1）.直接插入排序（Straiht Insertion Sort）

　　　　算法描述：如果有一个已经排好序的序列 {R(20),R(35),R(88)},当要插入一个R(66)时，需要与各个元素进行比较，R(35)<R(66)<R(88)，所以应该插在R(35)与R(88)直接。

　　　　算法开始时,取一个元素为原序列，然后重复执行上面的方法，将每个元素插入到序列中。

void InsertSort(SlList &L)
{
for(int i = 2; i < =L.lenght;i++)
            {
if(LT(L[i],L[i-1]))         //LT函数判断两个元素的大小 
                    {
                        L[0] = L[i];

　　　　　　　　　　　　　　L[i] = L[i-1];
for(int j = i-2;LT(L[0],L[j]);j--)
                             {
                                 L[j+1] = L[j];
                             }
                         L[j+1] = L[0];

             }



}

复制代码

此算法的时间复杂度为O(n²)

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　快速排序

快速排序是一种基于交换的排序方法，最常见的有冒泡排序（BubbleSort），快速排序（改进的冒泡排序）(QuickSort)

下面先说冒泡排序：

冒泡排序的基本思想是在一次排序中，将最大的元素沉入底部，然后缩小范围，继续进行。

具体的说：取第一个元素，然后与第二个元素进行比较，如果比第二个大，那么交换，否则，不交换，然后取第二个元素与第三个元素比较，同样用前面的方法，大则交换，直到将最大的元素交换到最底部，这是第一遍排序结束，然后，缩小范围，从第二个元素开始，在此运用上面的一遍排序方法。直到范围缩小为一个元素的时候，排序结束。

下面是用c++语言描述的一个冒泡排序的算法：

    int a[5] = {1,3,5,4,2};
for(int i=4;i>=0;i--)
for(int j = 0;j<=i;j++)
        {
if(a[j]>a[j+1])
            {
int temp;
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
for(int s = 0;s<5;s++)
        cout<<a[s];

复制代码

由于最近在学习汇编，所以在emu8086上写了一个代码段，实现冒泡排序：

 

;汇编冒泡排序算法
N equ 5
mov cx,N-1
j03:push cx
lea BX,A
j02:mov AL,[bx]
cmp AL,[BX+1]
jnb j01
xchg AL,[BX+1]
mov [BX],AL
j01:inc bx
loop j02
pop cx
loop j03  
A db 1,2,3,4,

复制代码

　　　　　　　　　　　　　　　　　　　　　选择排序

选择排序（Selection Sort）的基本思想是，每一趟排序在n-i+1（i=1，2，3....，n-1）中选取关键字最小的记录作为有序序列的第i个记录。

(1)最为简单的是简单选择排序（Sample Selection sort）

void selectsort(SqlList &L)
{
for(int i = 0;i < L.length;i++)
         {
            j = SelectMin*(L,i);//这个函数返回从i开始到结束的最小记录
//的位置
            if(i!=j) exchage(L[i],L[j]);

          }

}

复制代码

(2)树形选择排序(Tree Selection Sort)，又称锦标赛排序(Tournament sort)，是一种按照锦标赛的思想，两两比较，然后在剩余的【n/2】个较小的元素中在进行两两比较，如此重复，最后选出最小的记录为止。

（3）堆排序（Heap Sort）

先介绍一下大顶堆与小顶堆：

在一棵二叉树中，如果所有父节点比儿子节点都大，称这颗树为大顶堆，反之，为小顶堆。

那么堆排序的思想便是将一个无序序列构建成大顶堆（或小顶堆）然后取出堆顶元素，再次调整这个堆，使之在此变成大顶推（或小顶堆），如此将所有元素取出，便排好了序。

归并排序

归并排序（Merging sort）

所谓归并，简单的讲，就是将两个有序的序列，合成一个新的有序表。我们用这个思想，可以把一个n个元素的序列，看成n个长度为1的子序列，然后利用归并排序，两两合并，然后的到了n/2个长度为2的子序列，再次进行合并，重复上面的步骤，直到合并为一个序列，则归并完成。