首页 > 代码库 > 八大排序算法

八大排序算法

1:插入排序 - 直接插入排序


基本思想:

  将一个数字插入到已排好序的有序表当中,从而得到一个新的更大的有序表, 即将序列的第一个记录看成是一个有序的子序列, 然后将从第二个记录插入, 直至整个序列都有序为止.

技术分享

  如果发现一个和插入元素相等的,我们既可以将元素按照原来的顺序摆放得到稳定排序, 也可以改变位置得到不稳定排序.

  算法实现:   效率 O(n^2)

    void print(int a[], int n ,int i){  
        cout<<i <<":";  
        for(int j= 0; j<8; j++){  
            cout<<a[j] <<" ";  
        }  
        cout<<endl;  
    }  
      
      
    void InsertSort(int a[], int n)  
    {  
        for(int i= 1; i<n; i++){  
            if(a[i] < a[i-1]){               //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入  
                int j= i-1;   
                int x = a[i];        //复制为哨兵,即存储待排序元素  
                a[i] = a[i-1];           //先后移一个元素  
                while(x < a[j]){  //查找在有序表的插入位置  
                    a[j+1] = a[j];  
                    j--;         //元素后移  
                }  
                a[j+1] = x;      //插入到正确位置  
            }  
            print(a,n,i);           //打印每趟排序的结果  
        }  
          
    }  
      
    int main(){  
        int a[8] = {3,1,5,7,2,4,9,6};  
        InsertSort(a,8);  
        print(a,8,8);  
    }  

 

 2:插入排序 -希尔排序(Shell‘s Sort)


  希尔排序于1959年由D.L.Shell提出,相对于直接排序有较大的改进.希尔排序又称为缩小量排序.

基本思想:

  将整个待排序的记录序列分割成若干子序列分别进行直接插入排序, 待整个序列中的记录基本有序的时候, 再对全体记录进行依次直接插入排序.

操作方法:

  1:选择一个增量序列t1,t2,t3,...,tk,其中ti>tj, tk=1;

  2:按增量序列的个数k, 对序列进行k趟排序.

  3:每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m的子序列,分别对各个子表进行直接插入排序, 仅增量因子位1 时, 整个序列作为一个表来处理, 表长度位整个序列的长度.

技术分享

算法实现:

void shellsort(int a[], int n)
{
    int i, j, gap;

    for (gap = n / 2; gap > 0; gap /= 2) //gap4
        for (i = gap; i < n; i++)           //从4开始增加
            for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap) //
                swap(a[j], a[j + gap]);
}

 

 3:选择排序 - 简单选择排序(Simple Selection Sort)


基本思想:

  在要排序的一组数中,选出最小(最大也可以)的数组,和第一个数进行交换, 在剩下的数中选出第二小的和第二个数字进行交换,以此类推.

技术分享

操作方法:

  略

实现算法:

void SelectionSort(int a[],int n)
{
    int pos = 0,minPos = INT_MAX,selPos = 0,i;// 从 0 点开始
    for(;selPos<n;selPos++) // 从第一个位置开始排序.
    {
        for(i=selPos,minPos = INT_MAX;i<n;i++) // 找到目前最小数的坐标
        {
            if(a[i] < minPos)
            {
                pos = i;
                minPos = a[i];
            }
        }
        swap(a[pos],a[selPos]);
    }

}

 

4:选择排序 - 堆排序


 

   堆排序是一种树型选择排序,是对直接选择排序的有效改进.

基本思想:

  具有N个元素的序列(k1,k2,k3.......kn),当且仅当满足

技术分享

   时称为堆,由堆的定义可以看出,堆顶元素(即第一个元素)必须为最小项(小顶堆)

  若用一维数组储存一个堆,则堆对应一颗完全二叉树,且所有非叶结点的值均不大于其子女的值.

  (a) 大顶堆序列:(96,83,27,38,11,09)

  (b) 小顶堆序列:(12,36,24,85,47,30,53,91)

技术分享

  初始时要把排序的n个数的序列看做是一颗顺序储存的二叉树(一维数组储存的二叉树), 调整他们的储存顺序,使之成为一个堆, 讲堆顶元素输出,得到n个元素中的最小或者最大的元素, 这是堆的根节点的的数量最小或者最大,然后堆前面的(n-1)个节点重新调整使之称为新的堆,输出对应元素,得带n个元素中次大或者次小的元素. 以此类推,直到只有两个节点的堆

 

 

 

 

  

 

八大排序算法