算法-排序算法
冒泡排序
package com.sort;
//冒泡排序 時間復雜度O(n^2)
public class BubbleSort {
public static void main(String[] args) {
int[] arr={1,2,3,4,5};
int temp=0;
boolean flag=false;//判斷是否發(fā)生交換
for (int i = 0; i < arr.length-1; i++) {
for (int j = i+1; j < arr.length; j++) {
// 升序排列
if(arr[j]<arr[j-1]){
flag=true;
temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
}
if(!flag){
break;
}else{
flag=false;
}
}
for (int i:arr
) {
System.out.println(i);
}
}
}插入排序
package com.sort;
import java.util.Arrays;
//插入排序 時間復雜度O(n^2)
public class InsertSort {
public static void main(String[] args) {
int[] arr={1,44,787,33,74};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr){
for (int i = 1; i < arr.length; i++) {
for (int j = i; j >0 ; j--) {
if(arr[j]<arr[j-1]){
int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}else{
break;
}
}
}
}
}選擇排序
package com.sort;
import java.lang.reflect.Array;
import java.util.Arrays;
//選擇排序 時間復雜度O(n^2)
public class SelectSort {
public static void main(String[] args) {
int[] arr={12,87,44,78,7,67,34};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr){
for (int j = 0; j < arr.length-1; j++) {
int indexmin=j;
int min=arr[j];
for (int i = j+1; i < arr.length; i++) {
if(min > arr[i]){
min=arr[i];
indexmin = i;
}
}
if(indexmin != j) {
arr[indexmin] = arr[j];
arr[j] = min;
}
}
}
}希爾排序
package com.sort;
import java.util.Arrays;
//希爾排序 時間復雜度O(n long n)
public class ShellSort {
public static void main(String[] args) {
int[] arr = {2, 5, 8, 1, 4, 9, 7, 3, 0, 6};
// sort(arr);//交換法
sort2(arr);
System.out.println(Arrays.toString(arr));
}
// 交換法 不推薦
public static void sort(int[] arr) {
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
for (int j = i - gap; j >= 0; j -= gap) {
if (arr[j] > arr[j + gap]) {
int temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
}
}
// 移位法
public static void sort2(int[] arr){
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
int j=i;
int temp=arr[i];
if(arr[j]<arr[j-gap]){
while (j-gap>=0 && temp<arr[j-gap]){
arr[j]=arr[j-gap];
j-=gap;
}
arr[j]=temp;
}
}
}
}
}快速排序
package com.sort;
import java.util.Arrays;
//快速排序 時間復雜度O(n long n)
public class QuickSort {
public static void main(String[] args) {
int[] arr = {-1, -10, 6, 3, 0, 4};
sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr, int left, int right) {
int l = left;
int r = right;
int p = arr[(left + right) / 2];
int temp = 0;
while (l < r) {
while (arr[l] < p) {
l += 1;
}
while (arr[r] > p) {
r -= 1;
}
if (l >= r) {
break;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
if (arr[l] == p) {
r -= 1;
}
if (arr[r] == p) {
l += 1;
}
}
if (l == r) {
l += 1;
r -= 1;
}
if (left < r) {
sort(arr, left, r);
}
if (right > l) {
sort(arr, l, right);
}
}
}歸并排序
package com.sort;
import java.util.Arrays;
//歸并排序 時間復雜度O(n long n)
public class MergetSort {
public static void main(String[] args) {
int[] arr={11,3,16,8,4,5,0,8};
int[] temp=new int[arr.length];
sort(arr,0, arr.length-1,temp );
System.out.println(Arrays.toString(arr));
}
public 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);
}
}
public 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];
t++;
i++;
} else {
temp[t] = arr[j];
t++;
j++;
}
}
// 將剩余的傳入到temp數(shù)組中
while (i <= mid) {
temp[t] = arr[i];
t++;
i++;
}
while (j <= right) {
temp[t] = arr[j];
t++;
j++;
}
// 數(shù)組拷貝
t = 0;
int tempLeft = left;
while (tempLeft <= right) {
arr[tempLeft]=temp[t];
t++;
tempLeft++;
}
}
}基數(shù)排序
package com.sort;
import java.util.Arrays;
//基數(shù)排序 O(n*k)
//缺點：數(shù)組中不能含有負數(shù)，空間換時間，占用內存較大
public class RadixSort {
public static void main(String[] args) {
int[] arr={1,5,7,2,98,3,88,246,1478};
// int[] arr = new int[80000];
// for (int i = 0; i < arr.length; i++) {
// arr[i] = (int) (Math.random() * 8000);
// }
// 測試運行運行時間
// 開始時間
// long startTime = System.currentTimeMillis();
sort(arr);
// long endTime = System.currentTimeMillis();
// System.out.println("程序運行時間：" + (double) (endTime - startTime) / 1000 + "s");
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
int max = arr[0];
// 得到數(shù)組中的最大值
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 判斷數(shù)組中最大值的位數(shù)
int maxLength = (max + "").length();
// 定義一個二維數(shù)組，每一個一維數(shù)組就是一個桶
int[][] bucked = new int[10][arr.length];
// 定義一維數(shù)組，記錄每個桶中存放的數(shù)據(jù)
int[] backEleCount = new int[10];
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
// 取出每個元素個位值
int digitOfEle = arr[j] / n % 10;
// 存放到桶中
bucked[digitOfEle][backEleCount[digitOfEle]] = arr[j];
backEleCount[digitOfEle]++;
}
// 從一維數(shù)組中依次取出數(shù)據(jù)
int index = 0;
for (int j = 0; j < backEleCount.length; j++) {
if (backEleCount[j] != 0) {
// 遍歷第j個桶中的元素 放入到數(shù)組中
for (int k = 0; k < backEleCount[j]; k++) {
arr[index++] = bucked[j][k];
}
}
backEleCount[j] = 0;
}
}
}
}
浙公網(wǎng)安備 33010602011771號