image.png
各排序代码如下：
一：交换排序
// 冒泡排序
@Override
public void bubbleSort(int[] data) {
if (null == data || data.length <= 1) {
return;
}
final int length = data.length;
int temp = 0;
// 外层循环控制比较趟数 (每比较一趟，会确定一个数的最终位置, 会比较data.length - 1 趟)
for (int i = 0; i < length - 1; i++) { // 注意下标 结尾是 length - 1
// 内层循环是比较第[i]元素与，[i + 1, data.length]中所有元素的比较
for (int j = 0; j < length - 1 - i; j++) {
if (data[j + 1] < data[j]) {
temp = data[j + 1];
data[j + 1] = data[j];
data[j] = temp;
}
}
}
}
// 快速排序
@Override
public void quickSort(int[] data) {
if (null == data || data.length <= 1) {
return;
}
long startTime = System.currentTimeMillis();
inner_quickSort(data, 0, data.length - 1);
System.out.println("快速排序时间：" + (System.currentTimeMillis() - startTime));
}
private void inner_quickSort(int[] data, int start, int end) {
if (start < end) {
int i = partition(data, start, end);
inner_quickSort(data, start, i - 1);
inner_quickSort(data, i + 1, end);
}
}
private int partition(int[] array, int start, int end) {
int temp = array[start]; // 用子序的第一个作为基准
int i = start, j = end;
while (i < j) {
// 先遍历右边的数据
while (i < j && array[j] > temp) {
j--;
}
if (i < j) {
array[i] = array[j];
i++;
}
// 再遍历左边的数据
while (i < j && array[i] < temp) {
i++;
}
if (i < j) {
array[j] = array[i];
j--;
}
// array[i] = temp;
}
array[i] = temp;
return i;
}
二：选择排序
// 简单选择排序
@Override
public void simpleSelect(int[] data) {
if (null == data || data.length <= 1) {
return;
}
final int length = data.length;
for (int i = 0; i < length; i++) {
int target = i;
for (int j = i + 1; j < length; j++) {
if (data[j] < data[target]) {
target = j;
}
}
int temp = 0;
if (target != i) {
temp = data[target];
data[target] = data[i];
data[i] = temp;
}
}
}
// 堆排序
@Override
public void heapSort(int[] data) {
// TODO Auto-generated method stub
}
三： 插入排序
// 直接插入排序
@Override
public void directInsertSort(int[] data) {
for (int i = 1; i < data.length; i++) {
inner(data, 1, i);
}
}
// 希尔排序
@Override
public void shellSort(int[] data) {
int length = data.length;
for (int gap = length / 2; gap > 0; gap /= 2) {
for(int j = gap; j < length; j++) {
inner(data, gap, j);
}
}
}
private void inner(int[] data, int gap, int i) {
int willInsert = data[i];
int j;
for (j = i; j >= gap && data[j - gap] > willInsert; j -= gap) {
data[j] = data[j - gap];
}
data[j] = willInsert;
}
四： 归并排序
时间复杂度：O(nlogn)
空间复杂度：O(N) ，归并排序需要一个与原数组相同长度的数组来做辅助排序。
稳定性：是稳定的排序算法
@Override
public void mergeSort(int[] data) {
if (null == data || 1 >= data.length) {
return;
}
sort(data, 0, data.length - 1);
}
private void sort(int[] a, int start, int end) {
if (start < end) {// 当子序列中只有一个元素时结束递归
final int mid = (start + end) / 2;// 划分子序列
// 对左侧子序列进行递归排序
sort(a, start, mid);
// 对右侧子序列进行递归排序
sort(a, mid + 1, end);
// 合并
merge(a, start, mid, end);
}
}
// 两路归并算法，两个排好序的子序列合并为一个子序列
private void merge(int[] a, int left, int mid, int right) {
int[] tmp = new int[a.length];// 辅助数组
int p1 = left, p2 = mid + 1, tmpIndex = left;// p1、p2是检测指针，k是存放指针
// 比较左右两部分的元素，哪个小就把哪个元素填入tmp中
while (p1 <= mid && p2 <= right) {
tmp[tmpIndex++] = a[p1] <= a[p2] ? a[p1++] : a[p2++];
}
// 如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
// (以下两个while只有一个会执行)
while (p1 <= mid)
tmp[tmpIndex++] = a[p1++];
while (p2 <= right)
tmp[tmpIndex++] = a[p2++];
// 把最终的排序的结果复制给原数组
for (int i = left; i <= right; i++)
a[i] = tmp[i];
}
