/**
* Created with IntelliJ IDEA.
* Description:
* User: czt20
* Date: 2026 -01-19
* Time: 13:13
*/
public class sort {
//直接插入排序
/*时间复杂度；O(n^2);
* 空间复杂度；O(1);
* 稳定性；稳定(也可以不稳定)
* */
public static void insetSort(int[] arrays) {
for (int i = 1; i < arrays.length; i++) {
int j = i - 1;
int temp = arrays[i];
while (j >= 0) {
if (arrays[j] > temp) {
arrays[j + 1] = arrays[j];
arrays[j] = temp;
j--;
} else {
arrays[j + 1] = temp;
break;
}
}
}
}
public static void shellSort(int[] arrays) {
int gap = arrays.length;
while (gap > 1) {
gap /= 2;
shell(arrays, gap);
}
insetSort(arrays);
}
//希尔排序
/*时间复杂度(最坏)；O(n^2);
*时间复杂度(最好)；O(n);
* 空间复杂度；o(1);
* 不稳定排序
* */
private static void shell(int[] arrays, int gap) {
for (int i = gap; i < arrays.length; i++) {
int j = i - gap;
int temp = arrays[i];
while (j >= 0) {
if (arrays[j] > temp) {
arrays[j + gap] = arrays[j];
arrays[j] = temp;
j--;
} else {
// arrays[j + gap] = temp;
break;
}
}
}
}
//选择排序
/*
* 时间复杂度；O(N^2)
* 空间复杂度；O(1)
* 不稳定的排序
* */
public static void selectSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int mindIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[mindIndex]) {
mindIndex = j;
}
}
swap(array, i, mindIndex);
}
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void selectSort2(int[] array) {
int left = 0;
int right = array.length - 1;
while (left < right) {
int minIndex = left;
int maxIndex = left;
for (int i = left + 1; i <= right; i++) {
if (array[i] < array[minIndex]) {
minIndex = i;
}
if (array[i] > array[maxIndex]) {
maxIndex = i;
}
}
swap(array, left, minIndex);
if (maxIndex == left) {
maxIndex = minIndex;//////////////////////最大值正好是left
}
swap(array, right, maxIndex);
left++;
right--;
}
}
//堆排序
/*
时间复杂度；O(nlogK)
* 空间复杂度；O(1)
* 不稳定的排序
* */
public static void heapSort(int[] array) {
createHeap(array);
int end = array.length - 1;
while (end > 0) {
swap(array, 0, end);
shiftDown(array, 0, end);
}
}
private static void createHeap(int[] array) {
for (int paraent = (array.length - 1 - 1) / 2; paraent > 0; paraent--) {
shiftDown(array, paraent, array.length);
}
}
private static void shiftDown(int[] array, int paraent, int end) {
int child = 2 * paraent + 1;
while (child < end) {
if (child + 1 < end && array[child] < array[child + 1]) {
child++;
}
if (array[child] > array[paraent]) {
swap(array, paraent, child);
paraent = child;
child = 2 * paraent + 1;
} else {
break;
}
}
}
//冒泡排序
/*
*时间复杂度；O(N^2)
* 空间复杂度；O(1)
* 稳定的排序
* */
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
boolean flg = false;
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flg = true;
}
}
if (flg == false) {
break;
}
}
}
//快速排序
/*
时间复杂度；如果本身有序O(N^2), （默认）最好:O(NlogN);
* 空间复杂度；最好O(N),最坏O(logN);
* 不稳定的排序
* */
public static void QuicjSort(int[] array) {
qiuckNor(array, 0, array.length - 1);
}
//非递归快速排序
public static void qiuckNor(int[] array, int start, int end) {
Stack<Integer> stack = new Stack<>();
int pivot = partiton(array, start, end);
if (pivot > start + 1) {
stack.push(start);
stack.push(pivot - 1);
}
if (pivot < end - 1) {
stack.push(pivot + 1);
stack.push(end);
}
while (!stack.isEmpty()) {
int end2 = stack.pop();
int start2 = stack.pop();
partiton(array, start2, end2);
}
}
private static void qiuck(int[] array, int start, int end) {
if (start >= end) { //递归的结束语句
return;
}
int midIndex = getMiddleNumber(array, start, end);
swap(array, start, midIndex);
int pivot = partiton2(array, start, end);
qiuck(array, start, pivot - 1);
qiuck(array, pivot + 1, end);
}
private static int partiton(int[] array, int left, int right) {
int temp = array[left];
int templeft = left;
while (left < right) {
while (left < right && array[right] >= temp) {
right--;
}
while (left < right && array[left] <= temp) {
left++;
}
swap(array, left, right);
}
swap(array, left, templeft);
return left;
}
//挖坑法
private static int partiton2(int[] array, int left, int right) {
int temp = array[left];
int templeft = left;
while (left < right) {
while (left < right && array[right] >= temp) {
right--;
}
array[left] = array[right];
while (left < right && array[left] <= temp) {
left++;
}
array[right] = array[left];
}
array[left] = temp;
return left;
}
//三数取中(优化)
private static int getMiddleNumber(int[] array, int left, int right) {
int mid = (left + right) / 2;
return mid;
}
//霍尔法--前后指针............
/*归并排序
时间复杂度:O(NlogN);
* 空间复杂度；O(N);
* 稳定的排序(等号)
* */
public static void mergeSort(int[] array) {
mergeSortTmp(array, 0, array.length);
}
private static void mergeSortTmp(int[] array, int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
mergeSortTmp(array, left, mid);
mergeSortTmp(array, mid + 1, right);
// 分解完毕
// 合并
merge(array, left, mid, right);
}
private static void merge(int[] array, int left, int mid, int right) {
int[] tmp = new int[left + right];
int k = 0;
int s1 = left;
int e1 = mid;
int s2 = mid + 1;
int e2 = right;
while (s1 <= e1 && s2 <= e2) {
if (array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
} else {
tmp[k++] = array[s2++];
}
}
while (s1 <= e1) {
tmp[k++] = array[s1++];
}
while (s2 <= e2) {
tmp[k++] = array[s2++];
}
for (int i = 0; i < k; i++) {
array[i + left] = tmp[i];
}
}
/*非递归实现 归并排序
* */
public static void mergerSortNor(int[] array) {
int gap = 1;
while (gap < array.length) {
for (int i = 0; i < array.length; i = i + 2 * gap) {
int left = i;
int mid = left + i - 1;
if (mid > array.length) {
mid = array.length - 1;
}
int right = mid + gap;
if (right > array.length) {
right = array.length - 1;
}
merge(array, left, mid, right);
}
gap *= 2;
}
}
//计数排序：集中在一定范围的数据
/*时间复杂度；O(N+范围)
* 空间复杂度；O(范围)
* 稳定性；稳定
* */
public static int[] CountSort(int[] array) {
int maxVal = array[0];
int minVal = array[0];
for (int i = 1; i < array.length; i++) {
if (maxVal > array[i]) {
maxVal = array[i];
}
if (minVal < array[i]) {
minVal = array[i];
}
}
int len = maxVal - minVal;
int[] count = new int[len];
for (int i = 0; i < array.length; i++) {
count[array[i] - minVal]++;
}
int[] count2 = new int[len];
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] != 0) {
count2[index++] = i + minVal;
count[i]--;
}
}
return count2;
}
//桶排序......
}
查看3道真题和解析