排序算法

排序算法对于我们程序员来讲肯定是不陌生的，我们平时工作的过程中肯定也遇到需要对数据就行排序的情况。现在大多数的高级语言已经对这些排序算法进行封装，并且性能也很不错，但是了解这些算法背后的思想却是很有必要的，能够很好提升我们思维。

十大经典排序算法为：冒泡，选择，插入、希尔、归并、快速、堆、计数、桶、基数

/* 打印数组元素 */
void print_array(int arr[], int len)
{
    int i=0;
    for(i=0; i<len; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return ;
}

/* 测试函数 */
int main(int argc, char *argv[])
{
    int i = 0;
    int a[] = {5,4,9,8,7,6,0,1,3,2};
    print_array(a, sizeof(a)/sizeof(a[0])); 
    int len = sizeof(a)/sizeof(a[0]);
    // BubbleSort(a, sizeof(a)/sizeof(a[0]));
    SelectSort(a, sizeof(a)/sizeof(a[0]));
    print_array(a, sizeof(a)/sizeof(a[0]));
    return 0;
}

冒泡排序

（1）比较相邻的两个元素，如果第一个比第二个大，就交换他们。

（2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

（3）针对所有的元素重复以上的步骤，除了最后一个。

/* C语言代码实现 */
void BubbleSort(int array[], int len)
{
    int i, j;
    for (i = 0; i < len; i++)
    {
        for (j = 0; j < len-1-i; j++)
        {
            if (array[j] > array[j+1])
            {
                Swap(&array[j], &array[j+1]);
            }
        }
    }    
    return ;
}

选择排序

/* C语言代码实现 */
void SelectSort(int array[], int len)
{
    int i, j;
    int min, index;
    for ( i = 0; i < len-1; i++)
    {
        min = array[i];
        /* code */
        for ( j = i+1; j < len; j++)
        {
            if (min > array[j])
            {
                min = array[j];
                index = j;
            }
        }

        Swap(&array[i], &array[index]);
    }
        
    return;
}

插入排序

/* C语言代码实现 */
void InsertSort(int array[], int len){

    int i, j;
    int temp;
    for ( i = 1; i < len; i++)
    {
        temp = array[i];
        for ( j = i-1; j >=0; j--)
        {
            /* code */
            if (temp < array[j]){
                array[j+1] = array[j];
            }
            else
            {
                break;
            }
            
        }
        array[j+1] = temp;
    }
    return ;
}