一棵会开花的树
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) 量级，这两种排序算法的排序结果是不稳定的。
网友评论