七大排序

---

阅读目录

• 分类及比较
• 冒泡排序
• 快速排序
• 选择排序
• 插入排序
• 希尔排序
• 归并排序
• 堆排序

---

1.分类及比较

排序 比较.jpg

2.冒泡排序

基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。
过程:

• 比较相邻的两个数据，如果第二个数小，就交换位置。
• 从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。
• 继续重复上述过程，依次将第2.3...n-1个最小数排好位置。

代码:

void BubbleSort(int *pData,int Count)
{
    int iTemp;
    for(int i=0;i<Count-1;i++)
    {
        for(int j=Count-1;j>i;j--)
        {
            if(pData[j]<pData[j-1])
            {
                iTemp=pData[j-1];                
                pData[j-1]=pData[j];                
                pData[j]=iTemp;
            }
        }
    }
}

优化: 略

3.快速排序

基本思想:

• 先从数列中取出一个数作为key值；
• 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
• 对左右两个小数列重复第二步，直至各区间只有1个数。
  代码:

4.选择排序

基本思想:
在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
。。。
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
代码:

void SelectSort(int *a, int len){
    int tmp;
    for(int i=0; i<len-1; i++){
        int k=i;
        for(int j=i+1; j<len; j++){
            if(a[j]<a[k])
                k=j;
        }
        if(k!=i){
            tmp=a[i];
            a[i]=a[k];
            a[k]=tmp;
        }
    }
}

5.插入排序

基本思想:
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
代码:

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;      //插入到正确位置
        }
    }
}

6.希尔排序

基本思想:
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
代码:

/** 
 * 直接插入排序的一般形式 
 * 
 * @param int dk 缩小增量，如果是直接插入排序，dk=1 
 * 
 */  
  
void ShellInsertSort(int a[], int n, int dk)  
{  
    for(int i= dk; i<n; ++i){  
        if(a[i] < a[i-dk]){          //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入  
            int j = i-dk;     
            int x = a[i];           //复制为哨兵，即存储待排序元素  
            a[i] = a[i-dk];         //首先后移一个元素  
            while(x < a[j]){     //查找在有序表的插入位置  
                a[j+dk] = a[j];  
                j -= dk;             //元素后移  
            }  
            a[j+dk] = x;            //插入到正确位置  
        }  
        print(a, n,i );  
    }  
}  
  
/** 
 * 先按增量d（n/2,n为要排序数的个数进行希尔排序 
 * 
 */  
void shellSort(int a[], int n){  
    int dk = n/2;  
    while( dk >= 1  ){  
        ShellInsertSort(a, n, dk);  
        dk = dk/2;  
    }  
}

7.归并排序

基本思想:
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
首先考虑下如何将2个有序数列合并。这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

略

8. 堆排序

略