选择排序
直接选择排序
- 思想：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后每次从剩余未排序元素中继续寻找最小（大）元素放到已排序序列的末尾。以此类推，直到所有元素均排序完毕.
- 时间复杂度：最坏:O(n^2) 最好: O(n^2) 平均: O(n^2)
- 空间复杂度：O(1)
- 稳定性：不稳定 例如数组 2 2 1 3 第一次选择的时候把第一个2与1交换使得两个2的相对次序发生了改变。
<code>public static void selectSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int minIdx = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[minIdx]) {
minIdx = j;
}
}
exch(array, i, minIdx);
}
}
/<code>
堆排序
- 思想：堆排序是利用堆的性质进行的一种选择排序，先将排序元素构建一个最大堆,每次堆中取出最大的元素并调整堆。将该取出的最大元素放到已排好序的序列前面。这种方法相对选择排序，时间复杂度更低，效率更高。时间复杂度：最坏:O(nlog2n) 最好: O(nlog2n) 平均: O(nlog2n)空间复杂度：O(1)稳定性：不稳定 例如 5 10 15 10。 如果堆顶5先输出，则第三层的10(最后一个10)的跑到堆顶，然后堆稳定，继续输出堆顶，则刚才那个10跑到前面了，所以两个10排序前后的次序发生改变。
<code>// 第一个元素没有利用
public static void heapSort(int[] array) {
int N = array.length -1;
for (int k = N / 2; k >= 1; k--) { // k >= 1
sink(array, k, N);
}
while (N > 1) {
// 最大堆, 选择最大值放在最后
exch(array, 1, N --);
sink(array, 1, N);
}
}
private static void sink(int[] array, int k, int N){
while (2 * k <= N) {
int j = 2 * k;
if (j < N && array[j] < array[j+1]) { // <
j++;
}
if (array[j] < array[k]) break; // <
exch(array, k, j);
k = j;
}
}
/<code>
归并排序
- 思想：归并排序采用了分治算法，首先递归将原始数组划分为两个子数组，直到数组元素个数为1，对每个子数组进行排序。然后将排好序的子数组递归合并成一个有序的数组。
- 时间复杂度：最坏:O(nlog2n) 最好: O(nlog2n) 平均: O(nlog2n)
- 空间复杂度：O(n)
- 稳定性：稳定
代码：
<code>public static void mergeSort(int[] array) {
sort(array, 0, array.length - 1);
}
private static void sort(int[] array, int left, int right) {
if (left < right) {
int middle = (left + right) >> 1;
//递归处理相关的合并事项
sort(array, left, middle);
sort(array, middle + 1, right);
merge(array, left, middle, right);
}
}
private static void merge(int[] array, int lo, int mid, int hi) {
//创建一个临时数组用来存储合并后的数据
int[] temp = new int[array.length];
int left = lo;
int right = mid + 1;
int k = lo;
while (left <= mid && right <= hi) {
if (array[left] < array[right])
temp[k++] = array[left++];
else
temp[k++] = array[right++];
}
//处理剩余未合并的部分
while (left <= mid) temp[k++] = array[left++];
while (right <= hi) temp[k++] = array[right++];
//将临时数组中的内容存储到原数组中
while (lo <= hi) array[lo] = temp[lo++];
}
/<code>基数排序算法
- 思想：基数排序是通过“分配”和“收集”过程来实现排序，首先根据数字的个位的数将数字放入0-9号桶中，然后将所有桶中所盛数据按照桶号由小到大，桶中由顶至底依次重新收集串起来，得到新的元素序列。然后递归对十位、百位这些高位采用同样的方式分配收集，直到没各位都完成分配收集得到一个有序的元素序列。
- 时间复杂度：最坏:O(d(r+n)) 最好:O(d(r+n)) 平均: O(d(r+n))
- 空间复杂度：O(dr+n) n个记录，d个关键码，关键码的取值范围为r
- 稳定性：稳定 基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
为什么从底部取？因为桶内部是有序的，根据先进先出保证顺序
分享到:
閱讀更多 醉人Ryu 的文章
