1.冒泡算法
平均时间复杂度为O(n²);
从小到大排序：
形式1（把大数往右对齐，即右大对齐策略）：
public class bubbleSort {
public bubbleSort(){
int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
int temp=0;
for(int i=0;i<a.length-1;i++){
for(int j=0;j<a.length-1-i;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
}
}
形式2：（把小数往左对齐，即左小对齐策略）
public class bubble_sort {
static void bubble_sort(int[] unsorted)
{
for (int i = 0; i < unsorted.length; i++)
{
for (int j = i+1; j < unsorted.length; j++)
{
if (unsorted[i] > unsorted[j])
{
int temp = unsorted[i];
unsorted[i] = unsorted[j];
unsorted[j] = temp;
}
}
}
}
public static void main(String[] args)
{
int[] x = { 0, 6, 2, 4, 1, 5, 9 };
bubble_sort(x);
System.out.println(Arrays.toString(x));
}
}
2.快速排序：
时间复杂度为O(nlogn)
public static void quickSort(int[] arr, int startIndex, int endIndex) {
if(arr != null && arr.length > 0) {
int start = startIndex, end = endIndex;
//target是本次循环要排序的元素，每次循环都是确定一个元素的排序位置，这个元素都是开始下标对应的元素
int target = arr[startIndex];
//开始循环，从两头往中间循环，相遇后循环结束
while(start<end) {
//从右向左循环比较，如果比target小，就和target交换位置，让所有比target小的元素到target的左边去
while(start < end) {
if(arr[end] < target) {
swap(arr, start, end);
break;
}else {
end--;
}
}
//从左向右循环比较，如果比target大，就和target交换位置，让所有比target大的元素到target的右边去
while(start < end) {
if(arr[start] > target) {
swap(arr, start, end);
break;
}else {
start++;
}
}
}
//确定target的排序后，如果target左边还有元素，继续递归排序
if((start-1)>startIndex) {
quickSort(arr, startIndex, start-1);
}
//确定target的排序后，如果target右边还有元素，继续递归排序
if((end+1)<endIndex) {
quickSort(arr, end+1, endIndex);
}
}
}
参考：
https://blog.csdn.net/boy_chen93/article/details/85049274
https://blog.csdn.net/u011998957/article/details/88080093
3.归并排序
时间复杂度是O(nlogn)
public class MergeSort {
public static void main(String []args){
int []arr = {9,8,7,6,5,4,3,2,1};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int []arr){
int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
}
}
private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while(j<=right){//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}
}
参考：https://www.cnblogs.com/chengxiao/p/6194356.html
4.堆排
时间复杂度为O(nlogn)； 不稳定排序。
import java.util.Arrays;
/**
* 堆排序
*/
public class HeapSort {
public static void main(String []args){
int []arr = {11,7,18,3,5,4,1,6,10,9};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int []arr){
//1.构建大顶堆
for(int i=arr.length/2-1;i>=0;i--){
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(arr,i,arr.length);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for(int j=arr.length-1;j>0;j--){
swap(arr,0,j);//将堆顶元素与末尾元素进行交换
adjustHeap(arr,0,j);//重新对堆进行调整
}
}
/**
* 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
* @param arr
* @param i
* @param length
*/
public static void adjustHeap(int []arr,int i,int length){
int temp = arr[i];//先取出当前元素i
for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
k++;
}
if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
/**
* 交换元素
* @param arr
* @param a
* @param b
*/
public static void swap(int []arr,int a ,int b){
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
参考：https://www.cnblogs.com/chengxiao/p/6129630.html
5.插入排序
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
public static void insertionSort(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
for(int i = 1; i < nums.length; i++) {
for(int j = i - 1; j >= 0 && nums[j] > nums[j + 1]; j--) {
ArrayUtils.swap(nums, j, j + 1);
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
上面的算法的缺点：在第i-1趟插入时，需要把第i个元素插入到前面的i-1个元素中，该算法总是从i-1个元素开始逐个比较之前的每个元素，直到找到第i个元素的插入位置，这显然没有利用前面0~i-1个元素已经有序的特点
优化：在0~i-1个有序元素给第i个元素寻找插入的位置时，使用二分查找法可以有效提高查找插入位置的时间效率，经过优化的插入排序称为折半插入排序，折半插入排序的时间复杂度为O(n*logn)
/**
* 折半插入排序
*/
public static void binaryInsertionSort(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
for(int i = 1; i < nums.length; i++) {
int temp = nums[i];
// 通过二分查找找到插入的位置
int insertIndex = findInsertIndex(nums, 0, i - 1, nums[i]);
// 插入位置之后的元素依次向后移动
for(int j = i; j > insertIndex; j--) {
nums[j] = nums[j - 1];
}
// 更新插入位置的值
nums[insertIndex] = temp;
}
}
/**
* 在有序数组 nums 的[L, R]部分上，找到 value 的插入位置
*/
public static int findInsertIndex(int[] nums, int L, int R, int value) {
while(L <= R) {
int mid = L + ((R - L) / 2);
if(value > nums[mid]) {
L = mid + 1;
} else {
R = mid - 1;
}
}
return L;
}
参考：https://www.jianshu.com/p/d2cf77f78b3e
6.选择排序
时间复杂度 O(n²) 。
public class SelectionSort {
public static void main(String[] args) throws Exception {
int []arr = {11,7,18,3,5,4,1,6,10,9};
arr = sort(arr);
System.out.println(Arrays.toString(arr));
}
public static int[] sort(int[] sourceArray) throws Exception {
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// 总共要经过 N-1 轮比较
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
// 每轮需要比较的次数 N-i
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// 记录目前能找到的最小值元素的下标
min = j;
}
}
// 将找到的最小值和i位置所在的值进行交换
if (i != min) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
return arr;
}
}
参考：https://www.runoob.com/w3cnote/selection-sort.html
7.希尔排序
非稳定排序。
public static void shellSort(int[] arr){
int N = arr.length;
//进行分组，最开始的增量gap为数组长度的一半
for (int gap = N>>1; gap >0; gap>>=1) {
//对各个分组进行插入排序
for(int i=gap;i<N;i++){
//将arr[i]插入到所在分组的正确位置上
insertI(arr,gap,i);
}
}
}
/**
* @Author obrain
* @Description //将arr[i]查到所在分组的正确位置上
* @Date 14:16 2020/6/20
* @Param [arr, gap, i]
* @return void
*/
static void insertI(int[] arr, int gap, int i){
int temp = arr[i];
int j;
//插入时按组进行插入（组内元素两两相隔gap）
for ( j = i-gap; j>=0 && temp<arr[j]; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
参考：https://www.imooc.com/article/284892
8.双轴快排
单轴快排、双轴快排：参考：https://blog.csdn.net/Holmofy/article/details/71168530
9.更多算法参考