排序算法----常见的排序算法

算法分类 各算法特性

1.冒泡排序

void bubbleSort(int a[], int length) {
    int temp;
    for (int i = 0; i < length - 1; ++i) {
        for (int j = 0; j < length - 1 - i; ++j) {
            if (a[j] > a[j + 1]) {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

2.简单选择排序

void selectionSort(int a[], int length) {
    int temp, minIndex;

    for (int i = 0; i < length - 1; ++i) {

        //假设  a[i]  是当前最小值
        minIndex = i;

        //找数组后面是否还有  比 min更小的数
        for (int j = i + 1; j < length; ++j) {

            //如果  当前考察位置(a[j])  小于  a[minIndex]   则更新  索引
            if (a[j] < a[minIndex]) {
                //更新索引
                minIndex = j;
            }
        }

        //交换
        if (minIndex != i) {
            temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
}

3.直接插入排序

/**
 * 经典插入排序
 * @param arr
 * @param length
 */
void insertionSort(int *arr, int length) {
    int temp;
    for (int i = 1; i < length; ++i) {
        for (int j = i; j > 0 && arr[j - 1] > arr[j]; --j) {
            temp = arr[j - 1];
            arr[j - 1] = arr[j];
            arr[j] = temp;
        }
    }
}

/**
 * 优化的插入排序
 * @param arr
 * @param length
 */
void insertionSort1(int *arr, int length) {
    for (int i = 1; i < length; ++i) {
        int e = arr[i], j;
        for (j = i; j > 0 && arr[j - 1] > e; --j) {
            arr[j] = arr[j - 1];
        }
        arr[j] = e;
    }
}

4.快速排序

快速排序

5.堆排序

堆排序

6.希尔排序

希尔排序

7.归并排序

归并排序

8.基数排序

基数排序