排序算法

冒泡排序

/*
 * 开始用的是从n-1的元素进行比较，这是正规的冒泡排序算法
 */
void BubbleSort(int k[],int n)
{
    int i,j,temp;
    for (i = 0; i <n; i++) {
        for (j =n-1; j>i; j--) {
            if (k[j] < k[j-1]) {
                temp =k[j-1];
                k[j-1] = k[j];
                k[j] = temp;
            }
        }
    }
    for (int i =0 ; i<n; i++) {
        printf("%d ",k[i]);
    }
    printf("\n");
}

选择排序

void SelectSort(int k[],int n){
    int i,j,temp;
    for (i = 0; i<n; i++) {
        int min = i;
        for (j = i+1; j<n; j++) {
            if (k[j] < k[min]) {
                min = j;
            }
        }
        //如果i发生了变化，才会进行位置交换
        if (min != i) {
            temp = k[i];
            k[i] = k[min];
            k[min] = temp;
        }
    }
    for (int i =0 ; i<n; i++) {
        printf("%d ",k[i]);
    }
    printf("\n");
}

冒泡排序和选择排序的核心思路：

• 冒泡排序是：相邻两个元素两两进行比较，小则交换位置。
• 选择排序是：进行一轮比较，把最小的那个数拿出来。直到本轮比较完成后，才进行换位置。这样的效率在一定程度上高于冒泡排序。

直接插入排序

void InserSort(int k[],int n){
    int i,j,temp;

    for (i = 1; i<n; i++) {

        if (k[i] < k[i-1]) {
            //先保存最小值
            temp = k[i];
            //k[j] >temp核心的判断条件
            for (j = i-1; k[j] >temp; j--) {
                //找位置向后推移,
                k[j+1] = k[j];
            }
            printf("%d ",j);//打印结果为-1，所以k[j+1]其实就是k[0];
            k[j+1] = temp;

        }
    }
}

直接插入排序算的核心：

举例：

int k[] = {3,5,2};

第一次比较后，还是 3，5，2
第二次比较的详细过程：

    temp = 2；
    执行
    for (j = i-1; k[j] >temp; j--)
    {
        k[j+1] = k[j];
    }
    此时，j=1,k[1]=5>2;执行k[j+1] = k[j];
    所以，k[2]=5,
    现在的int k[]={3,5,5};

----------------------------------------------------------

    继续 j--,此时，j=0,k[0]=3>2；执行k[j+1] = k[j];
    所以，k[1]=3,
    现在的int k[]={3,3,5};

----------------------------------------------------------

    继续 j--，j=-1,跳出循环
    此时，
    现在的int k[]={3,3,5};
    执行  k[j+1] = temp;//j=-1
    现在的int k[]={2,3,5};

    完成