冒泡排序
冒泡排序的平均复杂度是O(N^2),最好的情况O(N),最坏的情况O(N^2);空间复杂度O(1);稳定算法
/**
* A为数组,n为数组的长度
*/
private static int[] bubbleSort(int[] A, int n) {
int temp;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (A[j] > A[j + 1]) {
temp = A[j + 1];
A[j + 1] = A[j];
A[j] = temp;
}
}
}
return A;
}
选择排序
选择排序时间复杂度 O(N^2),最坏的情况O(N^2);空间复杂度O(1);不稳定算法
/**
* A为数组,n为数组的长度
*/
private static int[] selectionSort(int[] A, int n) {
int minPos = 0;
int temp;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (A[j] < A[minPos]) {
minPos = j;
}
}
temp = A[minPos];
A[minPos] = A[i];
A[i] = temp;
minPos = i + 1;
}
return A;
}
插入排序
插入排序的平均复杂度是O(N^2),最好的情况O(N),最坏的情况O(N^2);空间复杂度O(1);稳定算法
/**
* A为数组,n为数组的长度
*/
private static int[] insertionSort(int[] A, int n) {
int temp;
for (int i = 2; i < n; i++) {
for (int j = 0; j < i; j++) {
if (A[i] < A[j]) {
temp = A[j];
A[j] = A[i];
A[i] = temp;
}
}
}
return A;
}
归并排序
归并排序时间复杂度O(N*logN),最好的情况O(N*logN),最坏的情况O(N*logN);空间复杂度O(N);稳定算法
/**
* A为数组,n为数组的长度
*/
private static int[] mergeSort(int[] A, int n) {
if (n > 1) {
int k = n / 2;
int[] temp1 = new int[k];
int[] temp2 = new int[n - k];
for (int i = 0; i < k; i++) {
temp1[i] = A[i];
}
for (int i = k; i < n; i++) {
temp2[i - k] = A[i];
}
temp1 = mergeSort(temp1, k);
temp2 = mergeSort(temp2, n - k);
int i = 0;
int j = 0;
int x = 0;
int[] temp = new int[n];
while (i < k && j < n - k) {
if (temp1[i] <= temp2[j]) {
temp[x] = temp1[i];
x++;
i++;
} else {
temp[x] = temp2[j];
x++;
j++;
}
}
while (i < k) {
temp[x] = temp1[i];
x++;
i++;
}
while (j < n - k) {
temp[x] = temp2[j];
x++;
j++;
}
return temp;
}
return A;
}
快速排序
快速排序的平均复杂度是O(N*logN),最好的情况O(N*logN),最坏的情况O(N^2);空间复杂度O(logN);不稳定算法
/**
* A为数组,n为数组的长度
*/
private static int[] quickSort(int[] A, int n) {
qSort(A, 0, n - 1);
return A;
}
/**
*
* @param A
* 数组
* @param start
* 数组起始位
* @param end
* 数组终止位
*/
public static void qSort(int[] A, int start, int end) {
if (start < end) {
Random random = new Random();
// 产生一个随机数
int nextInt = random.nextInt(end - start + 1) + start;
// 把随机位和数组最后一位交换
int temp = A[end];
A[end] = A[nextInt];
A[nextInt] = temp;
// 比A[nextInt]小的数的个数
int lt = 0;
for (int i = start; i < end; i++) {
if (A[i] <= A[end]) {
int temp1 = A[lt + start];
A[lt + start] = A[i];
A[i] = temp1;
lt++;
}
}
// 把数组最后一位和A[start + lt]交换
int temp2 = A[start + lt];
A[lt + start] = A[end];
A[end] = temp2;
// 递归
qSort(A, start, lt + start - 1);
qSort(A, lt + start + 1, end);
}
}
堆排序
时间复杂度 O(N*logN),最坏O(N*logN);不稳定算法
/**
* 从堆顶中取值,再重新建堆
*
* @param A
* 数组
* @param n
* 数组长度
* @return
*/
private static int[] heapSort(int[] A, int n) {
while (n > 0) {
sift(A, n);
int temp = A[n - 1];
A[n - 1] = A[0];
A[0] = temp;
n--;
sift(A, n);
}
return A;
}
/**
* 建堆
*
* @param A
* @param n
*/
public static void sift(int[] A, int n) {
// 最后一个非终端节点
int temp = n / 2;
while (temp > 0) {
int tt = 2 * temp - 1;
if (2 * temp <= n - 1) {
if (A[2 * temp] < A[2 * temp - 1]) {
tt = 2 * temp - 1;
} else {
tt = 2 * temp;
}
}
// 如果子节点大于父节点
if (A[temp - 1] < A[tt]) {
int t = A[temp - 1];
A[temp - 1] = A[tt];
A[tt] = t;
}
// 保证下面的堆为大顶堆
for (int i = (tt + 1); i <= n; i = 2 * i) {
int k = 2 * i - 1;
if (k < n) {
if (i * 2 + 1 <= n) {
if (A[2 * i] > A[2 * i - 1]) {
k = 2 * i;
}
}
if (A[i - 1] < A[k]) {
int t = A[i - 1];
A[i - 1] = A[k];
A[k] = t;
}
}
}
// 节点自减
temp--;
}
}
希尔排序
希尔排序的平均复杂度是O(N*logN)~O(N^2),最好的情况O(N^1.3),最坏的情况O(N^2);空间复杂度O(1);不稳定算法
/**
* A为数组,n为数组的长度
*/
private static int[] shellSort(int[] A, int n) {
Random random = new Random();
// 步长
int step = random.nextInt(n);
sSort(A,step);
return A;
}
/**
*
* @param A
* @param start
* 数组起始位
* @param end
* 数组终止位
*/
public static void sSort(int[] A, int step) {
// 当步长大于0时循环
while (step > 0) {
for (int i = step; i < A.length; i++) {
int k = i;
int temp = k - step;
while (temp >= 0) {
if (A[k] < A[temp]) {
int temp2 = A[k];
A[k] = A[temp];
A[temp] = temp2;
k = temp;
}
temp -= step;
}
}
// 步长自减
step--;
}
}
计数排序
时间复杂度 O(N);
/**
*
* @param A
* 数组
* @param n
* 数组长度
* @return
*/
private static int[] countingSort(int[] A, int n) {
int temp = A[0];
for (int i = 1;i<n ;i++) {
if(A[i]>temp){
temp = A[i];
}
}
int[] count = new int[temp+1];
for (int i = 0; i < n; i++) {
count[A[i]]++;
}
int[] result = new int[n];
int length = 0;
for (int i = 0; i < count.length; i++) {
while(count[i]>0){
result[length] = i;
count[i]--;
length++;
}
}
return result;
}
基数排序
时间复杂度 O (nlog(r)m),其中r为所采取的基数,而m为堆数;空间复杂度O(N);稳定算法
public static int[] radixSort(int[] A, int n) {
int index = 0;
for (int i = 1; i < n; i++) {
if (A[i] > A[index]) {
index = i;
}
}
int temp = A[index];
int count = 0;
while (temp / 10 > 0) {
count++;
temp /= 10;
}
count++;
int[][] bucket = new int[10][n + 1];
int temp1 = count;
while (count > 0) {
for (int i = 0; i < bucket.length; i++) {
bucket[i][0] = 0;
}
for (int i = 0; i < n; i++) {
int num;
if (temp1 - count == 0) {
num = A[i] % 10;
} else {
int tt = (int) Math.pow(10, temp1 - count);
num = (int) A[i] / tt % 10;
}
int length = bucket[num][0];
bucket[num][length + 1] = A[i];
length++;
bucket[num][0] = length;
}
int length = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < bucket[i][0]; j++) {
A[length] = bucket[i][j + 1];
length++;
}
}
count--;
}
return A;
}