Java 排序算法（冒泡、插入、选择、快速、希尔）

1、冒泡排序

• 基本思想

待排数据元素序列中的元素个数为 n。最多作 n-1 趟, i = 1, 2, ..., n-1。在第 i 趟中从后向前, j = n-1, n-2, ..., i, 两两比较 V[j-1] 和 V[j] 的关键字。如果发生逆序, 则交换 V[j-1] 和 V[j]。

• 实现过程

• 代码验证

// O(n*n)
void bubbleSort(int[] array, int len) {
    int i = 0;
    int j = 0;
    boolean exchange = true;
    
    for (i = 0; (i < len) && exchange; i++) {
        exchange = false;
        
        for (j = len-1; j > i; j--) {
            if (array[j] < array[j-1]) {
                swap(array, j, j-1);
                
                exchange = true;
            }
        }
    }
}

void swap(int[] array, int i, int j) {
    int temp = array[i];
    
    array[i] = array[j];
    
    array[j] = temp;
}

2、插入排序

• 基本思想

当插入第 i (i ≥ 1) 个数据元素时, 前面的 V[0], V[1], ..., V[i-1] 已经排好序。这时, 用 V[i] 的关键字与 V[i-1], V[i-2], ...,的关键字进行比较, 找到插入位置即将 V[i] 插入, 原来位置上的对象向后顺移。

• 实现过程

• 代码验证

// O(n*n)
void inertionSort(int[] array, int len) {
    int i = 0;
    int j = 0;
    int k = -1;
    int temp = -1;
    
    for (i = 1; i < len; i++) {
        k = i;
        temp = array[k];
        
        for (j = i-1; (j >= 0) && (array[j] > temp); j--) {
            array[j+1] = array[j];
            k = j;
        }
        
        array[k] = temp;
    }
}

3、选择排序

• 基本思想

每一趟 (例如第 i 趟, i = 0, 1, ..., n-2) 在后面 n-i 个待排的数据元素中选出关键字最小的元素, 作为有序元素序列的第 i 个元素。

• 实现过程

• 代码验证

// O(n*n)
void selectionSort(int[] array, int len) {
    int i = 0;
    int j = 0;
    int k = -1;
    
    for (i= 0; i < len; i++) {
        k = i;
        
        for (j = i; j < len; j++) {
            if (array[j] < array[k]) {
                k = j;
            }
        }
        
        swap(array, i, k);
    }
}

void swap(int[] array, int i, int j) {
    int temp = array[i];
    
    array[i] = array[j];
    
    array[j] = temp;
}

4、快速排序

• 基本思想

任取待排序序列中的某个数据元素（例如：第一个元素）作为基准，按照该元素的关键字大小将整个序列划分为左右两个子序列。** 左侧的子序列中所有元素都小于或等于基准元素，右侧的子序列中所有元素都大于或等于基准元素，基准元素排在这两个子序列中间。**分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。

• 实现过程

• 代码验证

// O(n*logn)
void quickSort(int array[], int len) {
    qSort(array, 0, len-1);
}

void qSort(int[] array, int low, int high) {
    if( low < high ) {
        int pivot = partition(array, low, high);
        
        qSort(array, low, pivot-1);
        qSort(array, pivot+1, high);
    }
}

int partition(int[] array, int low, int high) {
    int pv = array[low];
    
    while( low < high ) {
        while( (low < high) && (array[high] >= pv) ) {
            high--;
        }
        
        swap(array, low, high);
        
        while( (low < high) && (array[low] <= pv) ) {
            low++;
        }
        
        swap(array, low, high);
    }
    
    return low;
}

void swap(int[] array, int i, int j) {
    int temp = array[i];
    
    array[i] = array[j];
    
    array[j] = temp;
}

5、希尔排序

• 基本思想

将待排序列话费为若干组，在每一个组内进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排序。

• 实现过程

• 代码验证

// O(n*n) - O(n*logn)之间
void shellSort(int[] array, int len) {
    int i = 0;
    int j = 0;
    int k = -1;
    int temp = -1;
    int gap = len;
    
    do {
        gap = gap / 3 + 1; 
    
        for (i = gap; i < len; i += gap) {
            k = i;
            temp = array[k];
            
            for (j = i - gap; (j >= 0) && (array[j] > temp); j -= gap) {
                array[j+gap] = array[j];
                k = j;
            }
        
            array[k] = temp;
        }
        
    } while ( gap > 1 );
    
}

void swap(int[] array, int i, int j) {
    int temp = array[i];
    
    array[i] = array[j];
    
    array[j] = temp;
}

小结

• 冒泡排序、插入排序以及选择排序的算法思想简单，且算法的时间复杂度同为 O(n * n) 量级，这3种排序算法的排序结果都是稳定的。
• 快速排序和希尔排序将排序算法的时间复杂度提高到了 O(n * logn) 量级，这两种排序算法的排序结果是不稳定的。