* 三、交换排序
* 1、冒泡排序
* 1)、基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，
* 让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
* 2)、Java实现
*/
public static void bubbleSort(int[] a) {
// 冒泡排序
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length - i - 1; j++) {
// 这里-i主要是每遍历一次都把最大的i个数沉到最底下去了，没有必要再替换了
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
/*
* 3)、分析
* 冒泡排序是一种稳定的排序方法。
* •若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)
* •若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，
* 比较和移动次数均达到最大值∶O(n2)
* •起泡排序平均时间复杂度为O(n2)
* 2、快速排序
* 1)、基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,
* 一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用
* 同样的方法递归地排序划分的两部分。
* 2)、Java实现
*/
public static void quickSort(int[] a) {
if (a.length > 0) {
quickSort(a, 0, a.length - 1);
}
}
private static void quickSort(int[] a, int low, int high) {
if (low < high) { // 如果不加这个判断递归会无法退出导致堆栈溢出异常
int middle = getMiddle(a, low, high);
quickSort(a, 0, middle - 1);
quickSort(a, middle + 1, high);
}
}
private static int getMiddle(int[] a, int low, int high) {
int temp = a[low];// 基准元素
while (low < high) {
// 找到比基准元素小的元素位置
while (low < high && a[high] >= temp) {
high--;
}
a[low] = a[high];
while (low < high && a[low] <= temp) {
low++;
}
a[high] = a[low];
}
a[low] = temp;
return low;
}
/*
* 3)、分析
* 快速排序是不稳定的排序。
* 快速排序的时间复杂度为O(nlogn)。
* 当n较大时使用快排比较好，当序列基本有序时用快排反而不好。
*
* 四、归并排序
* 1、基本思想:归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表。
* 即把待排序序列分为若干个子序列，每个子序列是有序的。
* 然后再把有序子序列合并为整体有序序列。
* 2、Java实现
*/
public static void gbSort(int[] a) {
// 归并排序
mergeSort(a, 0, a.length - 1);
}
private static void mergeSort(int[] a, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
// 对左边进行递归
mergeSort(a, left, middle);
// 对右边进行递归
mergeSort(a, middle + 1, right);
// 合并
merge(a, left, middle, right);
}
}
private static void merge(int[] a, int left, int middle, int right) {
int[] tmpArr = new int[a.length];
int mid = middle + 1; // 右边的起始位置
int tmp = left;
int third = left;
while (left <= middle && mid <= right) {
// 从两个数组中选取较小的数放入中间数组
if (a[left] <= a[mid]) {
tmpArr[third++] = a[left++];
} else {
tmpArr[third++] = a[mid++];
}
}
// 将剩余的部分放入中间数组
while (left <= middle) {
tmpArr[third++] = a[left++];
}
while (mid <= right) {
tmpArr[third++] = a[mid++];
}
// 将中间数组复制回原数组
while (tmp <= right) {
a[tmp] = tmpArr[tmp++];
}
}
/*
* 3、分析
* 归并排序是稳定的排序方法。
* 归并排序的时间复杂度为O(nlogn)。
* 速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。
*
* 五、基数排序
* 1、基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，
* 依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
* 2、Java实现
*/
public static void baseSort(int[] a ) {
// 找到最大数，确定要排序几趟
int max = 0;
for (int i = 0; i < a.length; i++) {
if (max < a[i]) {
max = a[i];
}
}
// 判断位数
int times = 0;
while (max > 0) {
max = max / 10;
times++;
}
// 建立十个队列
List<ArrayList> queue = new ArrayList<ArrayList>();
for (int i = 0; i < 10; i++) {
ArrayList queue1 = new ArrayList();
queue.add(queue1);
}
// 进行times次分配和收集
for (int i = 0; i < times; i++) {
// 分配
for (int j = 0; j < a.length; j++) {
int x = a[j] % (int) Math.pow(10, i + 1)
/ (int) Math.pow(10, i);
ArrayList queue2 = queue.get(x);
queue2.add(a[j]);
queue.set(x, queue2);
}
// 收集
int count = 0;
for (int j = 0; j < 10; j++) {
while (queue.get(j).size() > 0) {
ArrayList<Integer> queue3 = queue.get(j);
a[count] = queue3.get(0);
queue3.remove(0);
count++;
}
}
}
}
/*
* 4、分析
*
* 基数排序是稳定的排序算法。
*
* 基数排序的时间复杂度为O(d(n+r)),d为位数，r为基数。
* |
收藏
淘帖
踩
