平均时间复杂度：不是O(n)
package work.icql.java.algorithm.sort.isnotN;
/**
* 冒泡排序：
* 1）稳定排序
* 2）算法思想
* 外层最大遍历元素个数
* 每一遍都会将当前未排序中最大的数排在最后面
* 里层的遍历是冒泡比较操作
* 3）平均时间复杂度：O(n^2)，平均空间复杂度：O(1)
*/
public class BubbleSort {
private BubbleSort() {
}
/**
* 第一版
*
* @param data
*/
public static void sort1(int[] data) {
//循环次数
//第一层循环，最大趟数 = length - 1
//第二层循环，最大交换次数 = length - 1 - 外层循环计数器
//因为数组末尾的有序区长度就是外层循环计数器的值
int count = data.length - 1;
for (int i = 0; i < count; i++) {
for (int j = 0; j < count - i; j++) {
//相邻位置 比较 交换
if (data[j] > data[j + 1]) {
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
}
/**
* 第二版：内层循环没有交换元素，则说明已经全部有序，所以直接返回
*
* @param data
*/
public static void sort2(int[] data) {
int count = data.length - 1;
for (int i = 0; i < count; i++) {
boolean isSorted = true;
for (int j = 0; j < count - i; j++) {
if (data[j] > data[j + 1]) {
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
isSorted = false;
}
}
if (isSorted) {
return;
}
}
}
/**
* 第三版：优化数组末尾的有序边界，有序边界应该为内层循环最后一次改变位置的地方
*
* @param data
*/
public static void sort3(int[] data) {
int count = data.length - 1;
int sortBorder = count;
int lastExchangeIndex = 0;
for (int i = 0; i < count; i++) {
boolean isSorted = true;
for (int j = 0; j < sortBorder; j++) {
if (data[j] > data[j + 1]) {
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
isSorted = false;
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
if (isSorted) {
return;
}
}
}
}
package work.icql.java.algorithm.sort.isnotN;
/**
* 插入排序：
* 1）稳定排序
* 2）算法思想
* 数据分为两个区间，已排序区间和未排序区间
* 插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序
* 重复这个过程，直到未排序区间中元素为空
* 3）平均时间复杂度：O(n^2)，平均空间复杂度：O(1)
*/
public class InsertionSort {
private InsertionSort() {
}
public static void sort1(int[] data) {
int count = data.length;
for (int i = 1; i < count; i++) {
//已排序区间的最后一个元素
int orderedIndex = i - 1;
int current = data[i];
while (orderedIndex >= 0 && current < data[orderedIndex]) {
data[orderedIndex + 1] = data[orderedIndex];
orderedIndex--;
}
data[orderedIndex + 1] = current;
}
}
public static void sort2(int[] data) {
int count = data.length;
for (int i = 1; i < count; i++) {
//已排序区间的最后一个元素
int orderedIndex = i - 1;
int current = data[i];
for (; orderedIndex >= 0; orderedIndex--) {
int prev = data[orderedIndex];
if (current < prev) {
data[orderedIndex + 1] = prev;
} else {
break;
}
}
data[orderedIndex + 1] = current;
}
}
}
package work.icql.java.algorithm.sort.isnotN;
/**
* 选择排序：
* 1）不稳定排序
* 2）算法思想
* 实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序
* 每次会从未排序区间中找到最小的元素，将其与已排序区间的末尾元素进行交换
* 3）平均时间复杂度：O(n^2)，平均空间复杂度：O(1)
*/
public class SelectionSort {
private SelectionSort() {
}
public static void sort(int[] data) {
int count = data.length;
for (int i = 0; i < count - 1; i++) {
// 寻找[i, 数组末尾)区间里的最小值的索引
int minIndex = i;
for (int j = i + 1; j < count; j++) {
if (data[j] < data[minIndex]) {
minIndex = j;
}
}
if (i != minIndex) {
int temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
}
package work.icql.java.algorithm.sort.isnotN;
import java.util.Arrays;
/**
* 归并排序：
* 1）稳定排序
* 2）算法思想
* 分治思想，要排序一个数组，我们先把数组从中间分成前后两部分
* 然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了
* 3）平均时间复杂度：O(nlogn)，平均空间复杂度：O(n)
*/
public class MergeSort {
private MergeSort() {
}
public static void sort(int[] data) {
sort(data, 0, data.length - 1);
}
private static void sort(int[] data, int left, int right) {
//不再继续分解
if (left >= right) {
return;
}
int mid = (left + right) / 2;
//左
sort(data, left, mid);
//右
sort(data, mid + 1, right);
//合并
merge(data, left, right, mid);
}
private static void merge(int[] data, int left, int right, int mid) {
//临时数组，用来保存当前用以归并的数据
int[] aux = Arrays.copyOfRange(data, left, right + 1);
int leftIndex = 0;
int leftIndexEnd = mid - left;
int rightIndex = leftIndexEnd + 1;
int rightIndexEnd = aux.length - 1;
//遍历重新设置 原数组 [left,right] 的值使之有序
for (int k = left; k <= right; k++) {
//左边元素已经处理完
if (leftIndex > leftIndexEnd) {
data[k] = aux[rightIndex];
rightIndex++;
continue;
}
//右边元素已经处理完
if (rightIndex > rightIndexEnd) {
data[k] = aux[leftIndex];
leftIndex++;
continue;
}
//如果左边所指元素 <= 右边所指元素
if (aux[leftIndex] <= aux[rightIndex]) {
data[k] = aux[leftIndex];
leftIndex++;
continue;
}
//如果左边所指元素 > 右边所指元素
data[k] = aux[rightIndex];
rightIndex++;
}
}
}
package work.icql.java.algorithm.sort.isnotN;
/**
* 快速排序：
* 1）不稳定排序
* 2）算法思想
* 分治思想，取任意点作为分区点，将小于分区点的数据放在分区点左边，将大于分区点的数据放在分区点右边
* 再分别对分区点两侧的数据做同样的操作，依次类推
* 3）平均时间复杂度：O(nlogn)，平均空间复杂度：O(1)
*/
public class QuickSort {
private QuickSort() {
}
public static void sort(int[] data) {
sort(data, 0, data.length - 1);
}
private static void sort(int[] data, int left, int right) {
if (left >= right) {
return;
}
//分区点，分区方法里 小于分区点-分区点-大于分区点
int pivot = partition(data, left, right);
sort(data, left, pivot - 1);
sort(data, pivot + 1, right);
}
/**
* 原地分区方法
*
* @param data
* @param left
* @param right
* @return
*/
private static int partition(int[] data, int left, int right) {
//选取分区点，右边界
int pivotIndex = right;
int pivotValue = data[pivotIndex];
int boarderIndex = left;
int borderValue = data[boarderIndex];
//遍历一遍
for (int i = left; i <= right; i++) {
int current = data[i];
//当游标值小于分区点值时，交换边界点和游标值
if (current < pivotValue) {
data[i] = borderValue;
data[boarderIndex] = current;
//更新边界点和边界索引
boarderIndex++;
borderValue = data[boarderIndex];
}
}
//交换边界点和分区点，更新分区点索引
data[right] = borderValue;
data[boarderIndex] = pivotValue;
pivotIndex = boarderIndex;
return pivotIndex;
}
}
TODO
平均时间复杂度：O(n)
package work.icql.java.algorithm.sort.isN;
/**
* 桶排序：
* 1）算法思想
* 将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。
* 桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了
* 2）平均时间复杂度：O(n)
*/
public class BucketSort {
private BucketSort() {
}
//比较适合用于外部排序
}
package work.icql.java.algorithm.sort.isN;
/**
* 计数排序：
* 1）算法思想
* 当所需排序的数据范围不大且有限，可以在桶排序的基础上，相等的数据放在一个桶
* 2）平均时间复杂度：O(n)
*/
public class CountingSort {
private CountingSort() {
}
}
package work.icql.java.algorithm.sort.isN;
/**
* 基数排序：
* 1）算法思想
* 比较数据的每一位，比如对手机号进行排序，可以先比较第一位，再比较第二位，以此类推
* 2）平均时间复杂度：O(n)
*/
public class RadixSort {
private RadixSort() {
}
}