2020-07-20
2020-07-20 本文已影响0人
遥望星空forward
各种排序算法的实现以及其时间复杂度和稳定性
//-------------------------------------------排序--------------------------------------------
/**
* 总结： 最优时间复杂度 最差时间复杂度 稳定性
*
* 冒泡排序 O(n) O(n^2) 稳定
*
* 选择排序 O(n^2) O(n^2) 不稳定
*
* 插入排序 O(n) O(n^2) 稳定
*
* 快速排序 O(nlogn) O(n^2) 不稳定
*
* 希尔排序 O(n^1.3) O(n^2) 不稳定
*
* 合并排序 O（nlogn） O(nlogn) 稳定
*
*
*/
public void invokeSort(){
int[] sort = {3, 4, 55, 21, 94, 49, 16, 89, 97, 56, 7};
// bubbleSort(sort);
// System.out.println("bubbleSort = " + Arrays.toString(sort));
// selectSort(sort);
// System.out.println("selectSort = " + Arrays.toString(sort));
// insertSort(sort);
// System.out.println("insertSort = " + Arrays.toString(sort));
// quickSort(sort, 0, sort.length - 1);
// System.out.println("quickSort = " + Arrays.toString(sort));
// shellSort(sort);
// System.out.println("shellSort = " + Arrays.toString(sort));
sort = mergeSort(sort);
System.out.println("mergeSort = " + Arrays.toString(sort));
int searchValue = 48;
boolean binarySearch = binarySearch(sort, searchValue);
System.out.println("binarySearch = " + binarySearch);
}
/**
* 冒泡排序
* 最优时间复杂度：O(n)（比如如果数组本来就是有序的，那么我们可以在第二个循环中给个Boolean值进行判断，如果经过一次外围
* 循环之后内循环中没有交换过数据，此时已经可以证明数组是有序的了，内循环就相当于执行了时间复杂度为O(1)的几行代码，此时就
* 可以退出循环排序了）
* 最差时间复杂度：O(n^2)（两次循环）
* 稳定性：稳定（冒泡排序循环过程中不会导致两个相同的数据进行交换，还是会保持原来的首尾顺序）
*
* @param sort
*/
private void bubbleSort(int[] sort) {
int length = sort.length;
for (int i = length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (sort[j] > sort[j + 1]) {
int middleValue = sort[j + 1];
sort[j + 1] = sort[j];
sort[j] = middleValue;
}
}
}
}
/**
* 选择排序
* 最优时间复杂度：O(n^2)（无法经过一次循环就能判断是否有序，因为哪怕数组是有序的，依然要执行相同顺序的代码）
* 最差时间复杂度：O(n^2)（两次循环）
* 稳定性：不稳定（举个例子，序列{5 8 5 2 9}，我们知道第一遍选择第1个元素5会和2交换，
* 那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法）
*
* @param sort
*/
private void selectSort(int[] sort) {
// 升序每次选择最大的情况
// int length = sort.length;
// for (int i = length ; i > 0 ; i--) {
// int maxValue = 0;
// for (int j = 1; j < i; j++) {
// if (sort[j] > sort[maxValue]) {
// maxValue = j;
// }
// }
// int middleValue = sort[i];
// sort[i] = sort[maxValue];
// sort[maxValue] = middleValue;
// }
// 降序每次选择最小的情况
int length = sort.length;
for (int i = 0; i < length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < length; j++) {
if (sort[j] < sort[minIndex]) {
minIndex = j;
}
}
int middleValue = sort[i];
sort[i] = sort[minIndex];
sort[minIndex] = middleValue;
}
}
/**
* 插入排序
* 最优时间复杂度： O(n)（比如本来就是有序的，那么进行插入的内循环应为一判断就退出内循环了，
* 那么内循环只是相当于执行固定的几句代码就退出循环了）
* 最差时间复杂度： O(n^2)（两次循环）
* 稳定性： 稳定（插入排序不改变相同元素之间的顺序）
*
* @param sort
*/
private void insertSort(int[] sort) {
int length = sort.length;
for (int i = 1; i < length; i++) {
for (int j = i; j > 0; j--) {
if (sort[j] < sort[j - 1]) {
int middleValue = sort[j - 1];
sort[j - 1] = sort[j];
sort[j] = middleValue;
} else {
break;
}
}
}
}
/**
* 快速排序
* 最优时间复杂度：O(nlogn)（当每次往下进行划分排序的时候都是等半的情况，此时的这种情况时间复杂度是logn）
* 最差时间复杂度：O(n^2)（考虑本来就有序的情况，此时往下划分都是只有完整的一半，
* 相当于冒泡排序或者选择排序每次循环都只找到了一个最值的情况）
* 稳定性：不稳定（比如：{5,2,7,9,10,2}的情况，当把5当做middle值，那么先从右边开始游标往左行驶时，把最后面的
* 那个2放到了5的位置，那么此时2的原始首尾顺序已经改变了）
*
* @param sort
*/
private void quickSort(int[] sort, int firstIndex, int lastIndex) {
if (firstIndex >= lastIndex) {
return;
}
int middleValue = sort[firstIndex];
int cursorFirst = firstIndex;
int cursorLast = lastIndex;
while (cursorFirst < cursorLast) {
while (cursorLast > cursorFirst && sort[cursorLast] >= middleValue) {
cursorLast--;
}
sort[cursorFirst] = sort[cursorLast];
while (cursorLast > cursorFirst && sort[cursorFirst] < middleValue) {
cursorFirst++;
}
sort[cursorLast] = sort[cursorFirst];
}
sort[cursorFirst] = middleValue;
quickSort(sort, firstIndex, cursorFirst - 1);
quickSort(sort, cursorFirst + 1, lastIndex);
}
/**
* 希尔排序
* 最优时间复杂度：根据步长序列的不同而不同，最好的情况是n1.3
* 最差时间复杂度：O(n^2)
* 稳定性： 不稳定（比如{5,1,1,6},此时步长为2时，第二个1会跟5对换，那么此时两个1的前后顺序就发生了变化）
*
* @param sort
*/
private void shellSort(int[] sort) {
int length = sort.length;
int step = length / 2;
while (step > 0) {
for (int i = step; i < length; i++) {
for (int j = i; j >= step; j = j - step) {
if (sort[j] < sort[j - step]) {
int temp = sort[j];
sort[j] = sort[j - step];
sort[j - step] = temp;
}
}
}
step = step / 2;
}
}
/**
* 归并排序
* 最优时间复杂度：nlogn（无论何种情况，都是等分往下一分为二）
* 最差时间复杂度：nlogn（一分为二）
* 稳定性：稳定（归并排序不改变相同元素之间的顺序）
*
* @param sort
*/
private int[] mergeSort(int[] sort) {
int length = sort.length;
if (length <= 1) {
return sort;
}
int num = length / 2;
int[] left = mergeSort(Arrays.copyOf(sort, num));
int[] right = mergeSort(Arrays.copyOfRange(sort, num, length));
return merge(left, right);
}
private int[] merge(int[] left, int[] right) {
int leftCursor = 0;
int rightCursor = 0;
int leftLength = left.length;
int rightLength = right.length;
int sort[] = new int[leftLength + rightLength];
int sortCursor = 0;
while (leftCursor < leftLength && rightCursor < rightLength) {
if (left[leftCursor] <= right[rightCursor]) {
sort[sortCursor] = left[leftCursor];
leftCursor++;
} else {
sort[sortCursor] = right[rightCursor];
rightCursor++;
}
sortCursor++;
}
for (int i = leftCursor; i < leftLength; i++) {
sort[sortCursor] = left[i];
sortCursor++;
}
for (int i = rightCursor; i < rightLength; i++) {
sort[sortCursor] = right[i];
sortCursor++;
}
return sort;
}
/**
* 二分查找
*
* @param sort
* @param searchValue
*/
private boolean binarySearch(int[] sort, int searchValue) {
int length = sort.length;
if (length == 0) {
return false;
}
int middle = length / 2;
if (searchValue == sort[middle]) {
return true;
} else if (searchValue > sort[middle]) {
return binarySearch(Arrays.copyOfRange(sort, middle + 1, length), searchValue);
} else {
return binarySearch(Arrays.copyOfRange(sort, 0, middle - 1), searchValue);
}
}
