算法实现
直接插入排序
public static void insertSort() {
for (int i = 1;
i < array.length;
i++) {
int tempdata = https://www.it610.com/article/array[i];
int j;
for (j = i - 1;
j>= 0;
j--) {
if (array[j] > tempdata) {
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = tempdata;
}
}
希尔排序
public static void shellSort() {
int d = array.length;
while (true) {
d = d / 2;
for (int x = 0;
x < d;
x++) {
for (int i = x + d;
i < array.length;
i = i + d) {
int temp = array[i];
int j;
for (j = i - d;
j >= 0 && array[j] > temp;
j = j - d) {
array[j + d] = array[j];
}
array[j + d] = temp;
}
}
if (d == 1) {
break;
}
}
}
冒泡排序
public static void bubbleSort() {
int temp;
int size = array.length;
for (int i = 0;
i < size - 1;
i++) {
for (int j = 0;
j < size - 1 - i;
j++) {
if (array[j] > array[j + 1])//交换两数位置
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
简单选择排序
public static void simpleChooseSort() {
//数组长度
int len = array.length;
for (int i = 0;
i < len;
i++) {
//记录当前位置
int position = i;
//找出最小的数,并用position指向最小数的位置
for (int j = i + 1;
j < len;
j++) {
if (array[position] > (array[j])) {
position = j;
}//endif
}//endfor
//交换最小数array[position]和第i位数的位置
int temp = array[i];
array[i] = array[position];
array[position] = temp;
}//endfor
}
快速排序
public static void quickSort(int[] array, int start, int end) {
if (start < end) {
int baseNum = array[start];
//选基准值
int midNum;
//记录中间值
int i = start;
int j = end;
do {
while ((array[i] < baseNum) && i < end) {
i++;
}
while ((array[j] > baseNum) && j > start) {
j--;
}
if (i <= j) {
midNum = array[i];
array[i] = array[j];
array[j] = midNum;
i++;
j--;
}
} while (i <= j);
if (start < j) {
quickSort(array, start, j);
}
if (end > i) {
quickSort(array, i, end);
}
}
}
归并排序
static class MergSort {
private static void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;
// 左指针
int j = mid + 1;
// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = a[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = a[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0;
k2 < temp.length;
k2++) {
a[k2 + low] = temp[k2];
}
}public static void mergeSort(int[] a, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左边
mergeSort(a, low, mid);
// 右边
mergeSort(a, mid + 1, high);
// 左右归并
merge(a, low, mid, high);
}
}
}
算法选择 1.数据规模较小
- 待排序列基本有序的情况下,可以选择直接插入排序;
- 对稳定性不作要求宜用简单选择排序,对稳定性有要求宜用插入或冒泡。
- 完全可以用内存空间,序列杂乱无序,对稳定性没有要求,快速排序,此时要付出log(N)的额外空间;
- 序列本身可能有序,对稳定性有要求,空间允许下,宜用归并排序。
- 对稳定性有求,则可考虑归并排序;
- 对稳定性没要求,宜用堆排序。
总结比较
文章图片
推荐阅读
- 关于HashSet与HashMap
- JZ-068-打印从 1 到最大的 n 位数
- Java算法|Java 实现OS调度算法之先来先服务算法(FCFS)
- Java算法|Java 实现OS调度算法之短进程优先算法(SJF)
- 选择排序,简单排序,冒泡排序,快速排序的java代码实现
- Java中反射的概念、意义、用法(适合新手阅读)
- 算法|Java算法系列3--基于链表自定义队列
- java无限级树生成算法,空间复杂度为O(2n)