[数据结构与算法]十大排序算法(java源码)

十大排序算法(java源码)：

1.选择排序：

package testTenSort;

import java.util.Arrays;

public class SelectSort {
	public static void main(String[] args) {
		int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		selectSort(arr);
	}

	static void selectSort(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			int minPos = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < arr[minPos]) {
					minPos = j;
					swap(arr, i, minPos);
				}
			}

		}
		print(arr);
		System.out.println();
		// 以数组的形式返回
		System.out.println(Arrays.toString(arr));
	}

	// 实现数组中两个位置的数作交换
	static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	// 实现数组的打印
	static void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + "  ");
		}
	}

}

2.冒泡排序：

package testTenSort;

import java.util.Arrays;

public class BubbleSort {
	public static void main(String[] args) {
		int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		bubbleSort(arr);
	}

	// 实现冒泡排序：
	static void bubbleSort(int[] arr) {
		// 分析循环要由内往外看
		// 外层循环：数组中有多少个数就需要多少次循环
		for (int i = arr.length - 1; i >= 0; i--) {
			// 内层循环：如果前面那个数大于它后面的那个数，两数交换
			for (int j = 1; j <= i; j++) {
				if (arr[j] < arr[j - 1])
					swap(arr, j, j - 1);
			}
		}
		// 以数组的形式返回
		System.out.println(Arrays.toString(arr));
	}

	// 实现数组中两个位置的数作交换
	static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

3.插入排序：

package testTenSort;

import java.util.Arrays;

public class InsertSort {
	public static void main(String[] args) {
		int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		insertSort(arr);
	}

	// 实现插入排序：
	static void insertSort(int[] arr) {
		for (int i = 1; i < arr.length; i++) {
			for (int j = i; j > 0; j--) {
				if (arr[j] < arr[j - 1])
					swap(arr, j, j - 1);
			}
		}
		// 以数组的形式返回
		System.out.println(Arrays.toString(arr));
	}

	static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

4.希尔排序：

package testTenSort;

import java.util.Arrays;

public class ShellSort {
	public static void main(String[] args) {
		int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		shellSort(arr);
		KnuthShellSort(arr);
	}

	// 实现希尔排序：升级版的插入排序
	static void shellSort(int[] arr) {
		for (int gap = arr.length / 2; gap > 0; gap /= 2) {
			for (int i = gap; i < arr.length; i++) {
				for (int j = i; j >= gap; j -= gap) {
					if (arr[j] < arr[j - gap])
						swap(arr, j, j - gap);
				}
			}
		}
		// 以数组的形式返回
		System.out.println(Arrays.toString(arr));
	}

	// Knuth序列实现希尔排序：
	static void KnuthShellSort(int[] arr) {
		// Knuth序列
		int h = 0;
		while (h <= arr.length) {
			h = h * 3 + 1;
		}
		for (int gap = h; gap > 0; gap = (gap - 1) / 3) {
			for (int i = gap; i < arr.length; i++) {
				for (int j = i; j > gap - 1; j -= gap) {
					if (arr[j] < arr[j - gap])
						swap(arr, j, j - gap);
				}
			}
		}
		// 以数组的形式返回
		System.out.println(Arrays.toString(arr));
	}

	static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

5.堆排序：

package testTenSort;

import java.util.Arrays;

public class HeapSort {
	public static void main(String[] args) {
		int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		heapSort(arr);
	}

	// 实现堆排序：
	static void heapSort(int[] arr) {
		// 初始建堆
		// 最后一个非叶子节点的下标为：(arr.length-1-1)/2即arr.length / 2 - 1
		for (int i = arr.length / 2 - 1; i >= 0; i--)
			heapify(arr, i, arr.length - 1);
		// 堆排序过程
		// 倒序遍历堆，堆中有多少个数就需要多少次循环
		for (int i = arr.length - 1; i >= 0; i--) {
			// 将根节点的值与本次循环的最后一个元素进行交换
			swap(arr, 0, i);
			// 每次交换后，从根节点开始调整堆结构使其重新变为大根堆
			heapify(arr, 0, i - 1);
		}
		// 以数组的形式返回
		System.out.println(Arrays.toString(arr));

	}

	// 调整堆结构使其重新变为大根堆：
	static void heapify(int[] arr, int i, int last_index) {
		// 令当前非叶子节点的下标为最大值下标
		int max = i;
		if (2 * i + 1 <= last_index && arr[2 * i + 1] > arr[max])
			// 记左子节点的下标为最大值下标
			max = 2 * i + 1;
		if (2 * i + 2 <= last_index && arr[2 * i + 2] > arr[max])
			// 记右子节点的下标为最大值下标
			max = 2 * i + 2;
		// 若最大值下标不等于当前非叶子节点的下标
		if (max != i) {
			// 将当前非叶子节点的值与当前最大值进行交换
			swap(arr, i, max);
			// 从最大值下标开始继续调整堆结构
			heapify(arr, max, last_index);
		}

	}

	static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

6.快速排序：

package testTenSort;

import java.util.Arrays;

public class QuickSort {
	public static void main(String[] args) {
		int[] arr = { 7, 3, 2, 10, 8, 1, 9, 5, 4, 6 };
		quickSort(arr, 0, arr.length - 1);
		// 以数组的形式返回
		System.out.println(Arrays.toString(arr));

	}
    //实现快速排序：
	static void quickSort(int[] arr, int leftBound, int rightBound) {
		if (leftBound >= rightBound)
			return;
		int mid = partition(arr, leftBound, rightBound);
		quickSort(arr, leftBound, mid - 1);
		quickSort(arr, mid + 1, rightBound);

	}
    //实现分区：
	static int partition(int[] arr, int leftBound, int rightBound) {
		int pivot = arr[rightBound];
		int left = leftBound;
		int right = rightBound - 1;
		while (left <= right) {
			while (left <= right && arr[left] <= pivot)
				left++;
			while (left <= right && arr[right] > pivot)
				right--;
			if (left <= right)
				swap(arr, left, right);
		}
		swap(arr, left, rightBound);
		return left;

	}

	static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

7.归并排序：

package testTenSort;

import java.util.Arrays;

public class MergeSort {
	public static void main(String[] args) {
		int[] arr = { 1, 2, 4, 7, 8, 3, 5, 6, 9 };
		mergeSort(arr, 0, arr.length - 1);
		// 以数组的形式返回
		System.out.println(Arrays.toString(arr));
	}

	// 实现归并排序：
	static void mergeSort(int[] arr, int left, int right) {
		if (left == right)
			return;
		// 分成两半
		int mid = (left + right) / 2;
		// 左边排序
		mergeSort(arr, left, mid);
		// 右边排序
		mergeSort(arr, mid + 1, right);
		// 左右归并
		merge(arr, left, mid + 1, right);
	}

	// 实现左右归并：
	// leftPtr指向左排序的第一位
	// rightPtr指向右排序的第一位
	// righeBound指向右边界
	static void merge(int[] arr, int leftPtr, int rightPtr, int righeBound) {
		int mid = rightPtr - 1;
		int[] temp = new int[righeBound - leftPtr + 1];
		int i = leftPtr;
		int j = rightPtr;
		int k = 0;
		while (i <= mid && j <= righeBound) {
			temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
		}
		while (i <= mid)
			temp[k++] = arr[i++];
		while (j <= righeBound)
			temp[k++] = arr[j++];
		for (int m = 0; m < temp.length; m++)
			arr[leftPtr + m] = temp[m];
	}
}

8.桶排序：

package testTenSort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;

public class BucketSort {
	public static void main(String[] args) {
		int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		bucketSort(arr);
	}

	// 实现桶排序：
	static void bucketSort(int[] arr) {
		// 先找到最大值和最小值
		int max = arr[0];
		int min = arr[0];
		for (int i = 1; i < arr.length; i++) {
			max = arr[i] > max ? arr[i] : arr[0];
			min = arr[i] < min ? arr[i] : arr[0];
		}
		// 确定桶的数量:固定用法
		int count = (max - min) / arr.length + 1;
		// 定义一个泛型为数组的数组，外层数组用于盛放桶的数量，内层数组用于盛放桶中的数据
		ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
		for (int i = 0; i < count; i++)
			buckets.add(new ArrayList<Integer>());
		// 遍历arr，把数据放在对应的桶里：固定用法
		for (int i = 0; i < arr.length; i++)
			buckets.get((arr[i] - min) / arr.length).add(arr[i]);
		// 对每个桶分别排序：桶排序的稳定性取决于此处的排序是否稳定
		for (int i = 0; i < buckets.size(); i++)
			// 此处可使用任意排序方法，为了方便此处使用了集合封装的排序方法
			Collections.sort(buckets.get(i));
		// 把每桶里的内容输出即完成排序
		int k = 0;
		// 外层循环：遍历桶的数量
		for (int i = 0; i < buckets.size(); i++) {
			// 得到第i个桶
			ArrayList<Integer> list = buckets.get(i);
			// 遍历每个桶中的数据拷贝给arr数组
			for (int j = 0; j < list.size(); j++)
				arr[k++] = list.get(j);
		}
		System.out.println(Arrays.toString(arr));
	}

	// 实现数组中两个位置的数作交换
	static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

9.计数排序：

package testTenSort;

import java.util.Arrays;

public class CountSort {
	public static void main(String[] args) {
		int[] arr = { 2, 4, 2, 3, 7, 1, 1, 0, 0, 5, 6, 9, 8, 5, 7, 4, 0, 9 };
		countSort(arr);
	}

	// 实现计数排序：
	static void countSort(int[] arr) {
		// 定义结果数组
		int[] result = new int[arr.length];
		// 找最大值
		int max = arr[0];
		for (int i = 1; i < arr.length; i++)
			max = arr[i] > max ? arr[i] : arr[0];
		// 定义计数数组：计数数组的大小为arr数组中的最大值+1(包含0)
		int[] count = new int[max + 1];
		// 遍历arr，把数据放在计数数组里,数的大小与数组下标相同，下标所对应的数值表示该数值在arr数组中出现的次数
		for (int i = 0; i < arr.length; i++) {
			count[arr[i]]++;
		}
		// System.out.println(Arrays.toString(count));
		// 将计数数组转化为次数累加数组：记录最后一个重复元素所在的位置
		for (int i = 1; i < count.length; i++) {
			count[i] = count[i] + count[i - 1];
		}
		// System.out.println(Arrays.toString(count));
		// 倒序遍历arr数组，结合次数累加数组记录的坐标，保证了计数排序的稳定性
		// 将arr数组中的值拷贝到结果数组result中
		for (int i = arr.length - 1; i >= 0; i--) {
			// 最后一个重复元素所在的位置为count[arr[i]]-1
			result[count[arr[i]] - 1] = arr[i];
			count[arr[i]]--;
		}
		// 以数组的形式返回
		System.out.println(Arrays.toString(result));
	}
}

10.基数排序：

package testTenSort;

import java.util.Arrays;

public class RadixSort {
	public static void main(String[] args) {
		int[] arr = { 2, 4, 2, 3, 7, 1, 1, 0, 0, 5, 6, 9, 8, 5, 7, 4, 0, 9 };
		radixSort(arr);
	}

	// 实现基数排序：
	static void radixSort(int[] arr) {
		// 找最大值
		int max = arr[0];
		for (int i = 1; i < arr.length; i++)
			max = arr[i] > max ? arr[i] : arr[0];
		// 分解数字：value/exp%10
		for (int exp = 1; max / exp > 0; exp *= 10) {
			// 创建桶数组，里面有10个桶
			int[] buckets = new int[10];
			// 创建temp数组
			int[] temp = new int[arr.length];
			// 计算每个桶中数据的个数
			for (int i = 0; i < arr.length; i++)
				buckets[arr[i] / exp % 10]++;
			// 计算每个桶中的累加数据
			for (int i = 1; i < buckets.length; i++)
				buckets[i] += buckets[i - 1];
			// 倒序遍历arr数组，结合次数累加数组记录的坐标，保证了基数排序的稳定性
			// 将arr数组中的值拷贝到临时数组temp中
			// 此处之所以将arr数组中的值拷贝到临时数组temp中而不是像计数排序一样直接拷贝到result数组中
			// 是因为在基数排序中本次操作位于循环中
			for (int i = arr.length - 1; i >= 0; i--) {
				temp[buckets[arr[i]] - 1] = arr[i];
				buckets[arr[i]]--;
			}
			// 将temp数组中的值拷贝到arr数组中
			for (int i = 0; i < temp.length; i++)
				arr[i] = temp[i];
		}
		// 以数组的形式返回
		System.out.println(Arrays.toString(arr));
	}
}

创作挑战赛

新人创作奖励来咯，坚持创作打卡瓜分现金大奖