排序算法
2017-08-17 本文已影响0人
小2斗鱼
冒泡排序：平均时间复杂度O(n^2)，最好情况O(n) 稳定排序
/**
* @param array 冒泡排序
* 时间复杂度O(n^2) 稳定排序
*/
public void buddleSort(int[] array) {
if (array.length == 0) {
return;
}
int temp = 0;
boolean flag = false;
for (int j = array.length - 1; j >= 0; j--) {
flag = false;
for (int i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1]) {
temp = array[i + 1];
array[i + 1] = array[i];
array[i] = temp;
flag = true;
}
}
if (!flag) {
break;
}
}
}
直接插入排序 平均时间复杂度O(n^2) 稳定排序
package sort;
public class InsertSort {
/**
* @param array 直接插入排序
* 平均时间复杂度O(n^2) 稳定排序
*/
public void insertSort(int[] array) {
if (array.length == 0) {
return;
}
for (int i = 1; i < array.length; i++) {
int temp = array[i];
int j = 0;
for (j = i; j >= 0 && array[i - 1] > temp; j--) {
array[i] = array[i - 1];
}
array[j] = temp;
}
}
}
希尔排序 平均时间复杂度O(n^1.3) 最坏情况O(n^2) 不稳定排序
package sort;
import java.util.Arrays;
public class ShellSort {
public void Shell_Sort(int[] data) {
for (int n = data.length / 2; n > 0; n = n / 2) {//定义增量序列消除逆序对
for (int i = 1; i < data.length; i++) {
int temp = data[i];
int j = 0;
for (j = i; j > 0 && data[j - 1] > temp; j--) {
data[j] = data[j - 1];
}
data[j] = temp;
}
}
}
}
直接选择排序 平均时间复杂度O(n^2) 不稳定
package sort;
public class SelectSort {
/**
* @param array
* 直接选择排序 平均时间复杂度O(n^2) 不稳定
*/
public void selectSort(int[] array) {
if (array.length == 0) {
return;
}
for (int i = 0; i < array.length; i++) {
int min = i;// 最小值索引
for (int j = i + 1; j < array.length; j++) {
if (array[min] > array[j]) {
min = j;
}
}
int temp = array[min] ^ array[i];
array[min] = array[min] ^ temp;
array[i] = array[i] ^ temp;
}
}
}
折半排序
package sort;
public class BinaryInsertSort {
/**
* @param array
* 折半查找只是减少了比较次数，但是元素的移动次数不变，所以时间复杂度为O(n^2) 稳定排序
*/
public void binaryInsertSort(int [] array){
if(array.length==0){
return ;
}
for(int i=1 ;i<array.length;i++){
int temp=1;
int j=0;
int left=0;
int right=i-1;
while(right>=left){
int middle=(left+right)/2;
if(array[middle]<array[temp]){
left=middle+1;
}else{
right=middle-1;
}
}
for(j=i;j>left;j--){
array[j]=array[j-1];
}
array[j]=temp;
}
}
}
快速排序 平均时间复杂度O(nlog^2n) 最坏情况O(n^2) 不稳定排序
package sort;
public class QuicklySort {
/**
* @param array
* 快速排序 平均时间复杂度O(nlog^2n) 最坏情况O(n^2) 不稳定排序
*/
public void quicklySort(int[] array) {
if (array.length == 0) {
return;
}
sort(array, 0, array.length - 1);
}
private void sort(int[] array, int left, int right) {
if (left < right) {
int middle = getMiddle(array, left, right);
sort(array, left, middle);
sort(array, middle + 1, right);
}
}
private int getMiddle(int[] array, int left, int right) {
int temp = array[left];
while (left < right) {
while (left < right && temp < array[right]) {
right--;
}
array[left] = array[right];
while (left < right && temp >= array[right]) {
left++;
}
array[right] = array[left];
}
array[left] = temp;
return left;
}
}
归并排序 时间复杂度O(nlog^2n) 辅助空间O(n) 稳定排序
package sort;
public class MergeSort {
/**
* @param array 归并排序 时间复杂度O(nlog^2n) 稳定排序
*/
public void mergeSort(int[] array) {
if (array.length == 0) {
return;
}
sort(array, 0, array.length - 1);
}
private void sort(int[] array, int left, int right) {
if (right > left) {
int middle = (left + right) / 2;
sort(array, left, middle);
sort(array, middle + 1, right);
merge(array, left, right, middle);
}
}
private void merge(int[] array, int left, int right, int middle) {
int[] tempArray = new int[array.length];
int p1 = left;
int p2 = middle + 1;
int pt = left;
while (p1 <= middle && p2 <= right) {
if (array[p1] <= array[p2]) {
tempArray[pt++] = array[p1++];
} else {
tempArray[pt++] = array[p2++];
}
}
while (p1 <= middle) {
tempArray[pt++] = array[p1++];
}
while (p2 <= middle) {
tempArray[pt++] = array[p2++];
}
while (left <= right) {
array[left] = tempArray[left];
left++;
}
}
}
堆排序 时间复杂度O(nlog2^n) 不稳定排序
package sort;
public class HeapSort {
/**
* @param array
* 堆排序 时间复杂度O(nlog2^n) 不稳定排序
*/
public void heapSort(int[] array) {
if (array.length == 0) {
return;
}
// 建立最大堆
int herf = array.length / 2;
for (int i = herf; i >= 0; i++) {
maxHeap(array, i, array.length);
}
// 沉淀 排序
for (int i = array.length - 1; i >= 0; i--) {
exchange(array, 0, i);
herf = (array.length - 1) / 2;
// 再建堆
for (int j = herf; j >= 0; j++) {
maxHeap(array, j, i);
}
}
}
private void maxHeap(int[] array, int i, int length) {
int root = i;
int leftChild = 2 * i + 1;
int rightChild = 2 * i + 1;
if (leftChild < length && array[leftChild] > array[root])
root = leftChild;
if (rightChild < length && array[rightChild] > array[root])
root = rightChild;
if (i != root) {
exchange(array, i, root);
// 递归构建子树
maxHeap(array, root, length);
}
}
/**
* @param array
* @param i
* @param root
* 交换
*/
private void exchange(int[] array, int i, int root) {
int temp = array[i] ^ array[root];
array[i] = array[i] ^ temp;
array[root] = array[root] ^ temp;
}
}
基数排序 时间复杂度O(d(r+n)) 辅助空间O(dr+n) 稳定排序
package sort;
import java.util.Arrays;
public class RadixSort {
/**
* @param array
* 基数排序 时间复杂度O(d(r+n)) 辅助空间O(dr+n) 稳定排序
*/
public static void radix_sort(int[] array) {
if (array.length == 0) {
return;
}
int max = 0;
for (int i = 0; i < array.length; i++) {
if (max < array[i])
;
max = array[i];
}
int bit = 0;
while (max > 0) {
max /= 10;
bit++;
}
// 定义桶
int[][] bucket = new int[10][array.length];
// 记录每个桶中元素的个数
int[] count = new int[10];
for (int w = 0; w < bit; w++) {
for (int i = 0; i < array.length; i++) {
int index = array[i] / (int) Math.pow(10, w) % 10;
// 将元素放入桶
bucket[index][count[index]++] = array[i];
}
// 取出元素
int k = 0;
for (int i = 0; i < 10; i++) {
if (count[i] != 0) {
for (int j = 0; j < count[i]; j++) {
array[k++] = bucket[i][j];
}
// 清空计数器
count[i] = 0;
}
}
}
}
}
