常用排序算法
package cn.yjs.javaSort;
/**
*
* @author pc
* 平均 最好 最坏 辅助空间 稳定性
* O(n^2) O(n) O(n^2) O(1) 稳定
*/
public class BubbleSort2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
//int[] array = new int [10];
int[] array = {2,45,23,75,54,3,6,565,86};
int len = array.length;
for(Integer n: array) {
System.out.print(n+" ");
}
System.out.println();
//从最后一个元素开始，两两比较，如果前面的元素大于后面的元素，把小的往上冒,每次都将最小的往上冒
for(int i=0; i<len-1; i++) {
//可以改进，当执行完下面的循环时，若flag还是false,说明前面的所有数字已经是有序的了，直接跳出循环
boolean flag=false;
for(int j=len-1; j>i; j--) {
if(array[j]<array[j-1]) {
int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
flag = true;
}
}
if(!flag)
break;
}
for(Integer n: array) {
System.out.print(n+" ");
}
System.out.println();
int[] array2 = {2,45,23,75,54,3,6,565,86};
int len2 = array.length;
for(Integer n: array2) {
System.out.print(n+" ");
}
System.out.println();
//把大的往下沉
//核心思想是一次有一个固定不动
for(int i=len2-1; i>0; i--) {
for(int j=i-1; j>=0; j--) {
if(array2[i]<array2[j]) {
int temp = array2[j];
array2[j] = array2[i];
array2[i] = temp;
}
}
}
for(Integer n: array2) {
System.out.print(n+" ");
}
System.out.println();
}
}
package cn.yjs.javaSort;
public class HeapSort2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array = {2,45,23,75,54,3,6,565,86};
int len = array.length;
for(Integer n: array) {
System.out.print(n+" ");
}
System.out.println();
//要想实现堆排序，首先得将数组转换为堆
//从最后一个非叶子节点(len/2-1, n0 = n2 +1 )开始执行下滤，将大的数据往上冒
//下标从0开始
for(int i=len/2-1; i>=0; i--) {
percDown(array, i, len);
}
//堆排序
for(int i=len-1; i>0; i--) {
swap(array, 0, i);
percDown(array, 0, i);
}
for(Integer n: array) {
System.out.print(n+" ");
}
System.out.println();
}
private static void swap(int[] array, int i, int len) {
int temp = array[i];
array[i] = array[len];
array[len] = temp;
}
private static int left(int i) {
// TODO Auto-generated method stub
return 2*i+1;
}
private static void percDown(int[] array, int i, int len) {
int temp = array[i]; //要下滤的元素
int child = 0;
//停止条件是不再有左子树
for(; left(i)<len; i=child) {
child = left(i); //左子树的索引
//考虑右子树不为空的情况,并且左孩子节点元素小于右孩子节点，将指针指向大的元素
if(child!=len-1 && array[child]<array[child+1]) {
//array[i] = array[child+1];
child++;
}
//如果大的元素大于父节点元素
if(array[i]<array[child]) {
//如果小于左孩子
array[i] = array[child];
}else {
//父节点大于左右孩子
break;
}
}
array[i] = temp;
}
}
package cn.yjs.javaSort;
/**
*
* @author pc
* 平均 最好 最坏 辅助空间 稳定性
* O(n^2) O(n) O(n^2) O(1) 稳定
*/
public class InsertSort2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array = {2,45,23,75,54,3,6,565,86};
int len = array.length;
for(Integer n: array) {
System.out.print(n+" ");
}
System.out.println();
//假设前面i-1个是有序的，将第i个元素和前面所有元素比较，若前面元素大于第i个元素，将前面元素后移，
//直到该元素大于前面的元素停止
for(int i=0; i<len; i++) {
int temp = array[i];
int j=i-1;
for(; j>=0 && array[j]>temp; j--) {
array[j+1] = array[j];
}
array[j+1] = temp; //因为第j个元素以及小于temp了，所以要加1
}
for(Integer n: array) {
System.out.print(n+" ");
}
System.out.println();
}
}
package cn.yjs.javaSort;
/**
*
* @author pc
* 平均 最好 最坏 辅助空间 稳定性
* O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
*/
public class MergeSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
//int[] array = {2,45,23,75,54,3,6,565,86};
int[] array = {2,3,4};
int len = array.length;
for(Integer n: array) {
System.out.print(n+" ");
}
System.out.println();
//分而治之 先分成小部分，再将小部分合并
int[] tempArray = new int[len];
mergeSort(array, tempArray, 0, len-1);
for(Integer n: array) {
System.out.print(n+" ");
}
System.out.println();
}
//原数组 保存临时排序后的数组，
public static void mergeSort(int[] array, int[] tempArray, int start, int end) {
if(start>=end) {
return;
}
if(start<end) {
int mid = (start+end)/2;
mergeSort(array, tempArray, start, mid); //前半部分
mergeSort(array, tempArray, mid+1, end); //后半部分
//合并小部分
merge(array, tempArray, start, mid+1, end);
}
}
public static void merge(int[] array, int[] tempArray, int leftStart, int rightStart, int rightEnd) {
int leftEnd = rightStart-1;
int newIndex = leftStart; //不是从0开始
//int tempIndex = leftStart;
int tempIndex = 0; //不是0
int numOfEle = rightEnd-leftStart+1;
while(leftStart<=leftEnd && rightStart<=rightEnd) {
if(array[leftStart]< array[rightStart]) {
tempArray[tempIndex++] = array[leftStart++];
}
else {
tempArray[tempIndex++] = array[rightStart++];
}
}
while(leftStart<=leftEnd) {
tempArray[tempIndex++] = array[leftStart++];
}
while(rightStart<=rightEnd) {
tempArray[tempIndex++] = array[rightStart++];
}
/*for(int i=0; i<numOfEle; i++,rightEnd--) {
array[rightEnd] = tempArray[rightEnd];
}*/
for(int i=0; i<numOfEle; i++) {
array[newIndex++] = tempArray[i];
}
}
}
package cn.yjs.javaSort;
/**
*
* @author pc
* 平均 最好 最坏 辅助空间 稳定性
* O(nlogn) O(nlogn) O(nlogn) O(nlogn)~O(n) 不稳定
*/
public class QuickSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array = {2,45,23,75,54,3,6,565,86};
//int[] array = {2,3,4};
int len = array.length;
for(Integer n: array) {
System.out.print(n+" ");
}
System.out.println();
quickSort(array, 0, len-1);
for(Integer n: array) {
System.out.print(n+" ");
}
System.out.println();
}
public static void quickSort(int[] array, int left, int right) {
// TODO Auto-generated method stub
if(left<right) {
int mid = median(array, left, right); //得到选择枢纽（即对照值）
int start = left;
int end = right-1;
while(start<end) {
while(array[start]<mid) {start++;} //注意等于也会跳出，所以是不稳定的
while(array[end]>mid) {end--;}
if(start<end) {
swap(array, start, end);
}
}
swap(array, start, right); //将中间元素复位 将start的和对照值元素交换
quickSort(array, left, start-1);
quickSort(array, start+1, right);
}
}
public static int median(int[] array, int left, int right) {
// TODO Auto-generated method stub
int mid = (left+right)/2;
//使得左边小于中间
if(array[left]>array[mid]) {
swap(array, left, mid);
}
//使得左边小于右边，即左边最小
if(array[left]>array[right]) {
swap(array, left, right);
}
if(array[mid]>array[right]) {
swap(array, mid, right);
}
swap(array, mid, right); //使得选择枢纽处于最右边
return array[right];
}
public static void swap(int[] array, int i, int j) {
// TODO Auto-generated method stub
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
package cn.yjs.javaSort;
/**
*
* @author pc
* 平均 最好 最坏 辅助空间 稳定性
* O(n^2) O(n^2) O(n^2) O(1) 稳定
*/
public class SelectSort2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array = {2,45,23,75,54,3,6,565,86};
int len = array.length;
for(Integer n: array) {
System.out.print(n+" ");
}
System.out.println();
//每次选择最小（大）的元素，记录其索引，然后交换固定的元素和最小值（最小值索引对应的值）
//思想和冒泡排序差不多，都是一次固定一个，然后和其他所有吧元素相比较，但是不同点在于选择排序只在最后一次交换元素
for(int i=0; i<len-1; i++) {
int minIndex = i;
for(int j=i+1; j<len; j++) {
if(array[j]<array[minIndex]) {
minIndex = j;
}
}
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
for(Integer n: array) {
System.out.print(n+" ");
}
System.out.println();
}
}
package cn.yjs.javaSort;
/**
*
* @author pc
* 平均 最好 最坏 辅助空间 稳定性
* O(nlogn)~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定
*/
public class ShellSort2 {
public static void main(String[] args) {
int[] array = {2,45,23,75,54,3,6,565,86};
/*int nn= 5;
System.out.println(array[nn--]); //先取值，再--
System.out.println();
System.out.println();*/
int len = array.length;
for(Integer n: array) {
System.out.print(n+" ");
}
System.out.println();
//保证间隔距离为gap的序列有序
//gap初始值为len, 更新公式为gap = gap/3+1;
//当gap>1时一直执行
int gap=len;
while(gap>1) {
gap = gap/3+1;
for(int i=gap; i<len; i++) {
for(int j=i; j>=gap && array[j]<array[j-gap]; j-=gap) {
int temp = array[j];
array[j] = array[j-gap];
array[j-gap] = temp;
}
}
}
for(Integer n: array) {
System.out.print(n+" ");
}
System.out.println();
}
}