文章目录
常见算法分类
算法复杂度
算法描述与实现
交换类排序
冒泡排序
算法思想：
算法步骤：
稳定性：稳定排序
复杂度:
⽰例代码：
public class BubleSort {
public static void main(String[] args) {
int[] arr = { 1, 3, 2, 5, 4, 6, 100, 20 };
bubbleSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// 外层循环控制遍历次数
for (int j = 0; j < arr.length - 1 - i; j++) {
// 内层循环控制每次遍历比较的位置
if (arr[j] > arr[j + 1]) {
// 如果相邻元素顺序错误，交换它们的位置
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
具体的过程可以这样解释：
快速排序
算法原理：
稳定性：不稳定排序
复杂度：
⽰例代码：
public class QuickSort {
public static void main(String[] args) {
int arr[]={3,1,23,3,1,4,5,199,20};
new QuickSort().quickSort(arr, 0, arr.length-1);
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
}
public void quickSort(int[] arr, int start, int end) {
if (start < end) {
int pivot = partition(arr, start, end);
quickSort(arr, start, pivot - 1);
quickSort(arr, pivot + 1, end);
}
}
public int partition(int[] arr, int start, int end) {
int pivot = arr[start];
int left = start + 1;
int right = end;
while (left <= right) {
while (left <= right && arr[left] < pivot) {
left++;
}
while (left <= right && arr[right] >= pivot) {
right--;
}
if (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
int temp = arr[start];
arr[start] = arr[right];
arr[right] = temp;
return right;
}
}
插⼊类排序
直接插入排序
原理：
稳定性：稳定排序
复杂度：
⽰例代码：
public class InsertSort {
public static void main(String[] args) {
int[] arr = { 1, 3, 2, 5, 4, 6, 100, 20 };
insertionSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int j = i - 1;
int temp = arr[i];
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
}
说明：
Shell排序
稳定性：不稳定排序。
复杂度：
示例代码：
public class ShellSort {
public static void main(String[] args) {
int arr[] = { 3, 1, 23, 3, 1, 4, 5, 199, 20 };
shellSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
}
选择类排序
简单选择排序（⼜称直接选择排序）
原理：
稳定性：不稳定排序
时间复杂度：
⽰例代码：
public static void selectionSort(int[] arr){
int n = arr.length;
for(int i = 0; i < n - 1; i++){
int minIndex = i;
for(int j = i + 1; j < n; j++){
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
基本思想：
堆排序
原理：
稳定性: 不稳定排序
复杂度：
示例代码：
public class HeapSort {
public static void main(String[] args) {
int arr[] = { 3, 1, 23, 3, 1, 4, 5, 199, 20 };
heapSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void heapSort(int[] arr){
int n = arr.length;
// 构建大根堆
for(int i = n / 2 - 1; i >= 0; i--){
adjustHeap(arr, i, n);
}
// 进行排序
for(int i = n - 1; i > 0; i--){
swap(arr, 0, i);
adjustHeap(arr, 0, i);
}
}
private static void adjustHeap(int[] arr, int i, int n){
int temp = arr[i];
for(int j = 2 * i + 1; j < n; j = 2 * j + 1){
if(j + 1 < n && arr[j + 1] > arr[j]){
j++;
}
if(arr[j] > temp){
arr[i] = arr[j];
i = j;
}else{
break;
}
}
arr[i] = temp;
}
private static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
归并排序
二路归并排序
算法思想：
稳定性：稳定排序算法；
示例代码：
public class MergeSort {
public static void main(String[] args) {
int arr[] = { 3, 1, 23, 3, 1, 4, 5, 199, 20 };
mergeSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void mergeSort(int[] arr){
int n = arr.length;
int[] temp = new int[n];
sort(arr, 0, n - 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, j = mid + 1, k = 0;
while(i <= mid && j <= right){
if(arr[i] <= arr[j]){
temp[k++] = arr[i++];
}else{
temp[k++] = arr[j++];
}
}
while(i <= mid){
temp[k++] = arr[i++];
}
while(j <= right){
temp[k++] = arr[j++];
}
for(int p = 0; p < k; p++){
arr[left + p] = temp[p];
}
}
}
算法思想：
多路排序
示例代码：
public class MultMergeSort {
public static void main(String[] args) {
int arr[] = { 3, 1, 23, 3, 1, 4, 5, 199, 20 };
mergeSort(arr,3);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void mergeSort(int[] arr, int m){
int n = arr.length;
int[] temp = new int[n];
sort(arr, 0, n - 1, temp, m);
}
private static void sort(int[] arr, int left, int right, int[] temp, int m){
if(left < right){
int len = (right - left + 1) / m;
for(int i = 0; i < m; i++){
int l = left + i * len;
int r = l + len - 1;
if(i == m - 1){
r = right;
}
sort(arr, l, r, temp, m);
}
merge(arr, left, right, temp, m);
}
}
private static void merge(int[] arr, int left, int right, int[] temp, int m){
int[] p = new int[m];
int len = (right - left + 1) / m;
for(int i = 0; i < m; i++){
p[i] = left + i * len;
}
int k = left;
while(k <= right){
int min = Integer.MAX_VALUE;
int idx = -1;
for(int i = 0; i < m; i++){
if(p[i] <= left + i * len + len - 1 && arr[p[i]] < min){
min = arr[p[i]];
idx = i;
}
}
if(idx == -1){
break;
}
temp[k++] = arr[p[idx]++];
}
for(int i = left; i <= right; i++){
arr[i] = temp[i];
}
}
}
算法基本思想：
线性时间非比较类排序
计数排序
复杂度:
算法原理：
算法步骤：
复杂度：
稳定性：稳定。
代码⽰例：
public class CountSort {
public static void main(String[] args) {
int arr[] = { 3, 1, 23, 3, 1, 4, 5, 199, 20 };
countSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void countSort(int[] arr){
int max = arr[0], min = arr[0];
for(int i = 1; i < arr.length; i++){
if(arr[i] > max){
max = arr[i];
}else if(arr[i] < min){
min = arr[i];
}
}
int[] count = new int[max - min + 1];
for(int i = 0; i < arr.length; i++){
count[arr[i] - min]++;
}
int k = 0;
for(int i = 0; i < count.length; i++){
for(int j = 0; j < count[i]; j++){
arr[k++] = i + min;
}
}
}
}
注意：计数排序是典型的以空间换时间的排序算法，对待排序的数据有严格的要求，⽐如待排序的数值中包含负数，最⼤值都有限制，请谨慎使⽤。
思想：
基数排序
稳定性：稳定的排序
复杂度:
示例代码：
public class RadixSort {
public static void main(String[] args) {
int arr[] = { 3, 1, 23, 3, 1, 4, 5, 199, 20 };
radixSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void radixSort(int[] arr){
int max = arr[0];
for(int i = 1; i < arr.length; i++){
if(arr[i] > max){
max = arr[i];
}
}
int exp = 1;
int[] temp = new int[arr.length];
while(max / exp > 0){
int[] count = new int[10];
for(int i = 0; i < arr.length; i++){
count[(arr[i] / exp) % 10]++;
}
for(int i = 1; i < 10; i++){
count[i] += count[i - 1];
}
for(int i = arr.length - 1; i >= 0; i--){
temp[--count[(arr[i] / exp) % 10]] = arr[i];
}
for(int i = 0; i < arr.length; i++){
arr[i] = temp[i];
}
exp *= 10;
}
}
}
基本思想：
桶排序
思想：
排序过程：
稳定性：稳定的排序算法
复杂度：
⽰例代码：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
//桶排序
public class BucketSort {
public static void main(String[] args) {
int arr[] = { 3, 1, 23, 3, 1, 4, 5, 199, 20 };
bucketSort(arr,3);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void bucketSort(int[] arr, int bucketSize){
if(arr.length == 0){
return;
}
int max = arr[0], min = arr[0];
for(int i = 1; i < arr.length; i++){
if(arr[i] > max){
max = arr[i];
}else if(arr[i] < min){
min = arr[i];
}
}
int bucketCount = (max - min) / bucketSize + 1;
List<List<Integer>> buckets = new ArrayList<>();
for(int i = 0; i < bucketCount; i++){
buckets.add(new ArrayList<Integer>());
}
for(int i = 0; i < arr.length; i++){
int bucketIndex = (arr[i] - min) / bucketSize;
buckets.get(bucketIndex).add(arr[i]);
}
int k = 0;
for(int i = 0; i < bucketCount; i++){
List<Integer> bucket = buckets.get(i);
Collections.sort(bucket);
for(int j = 0; j < bucket.size(); j++){
arr[k++] = bucket.get(j);
}
}
}
}
思想：