黑马程序员技术交流社区
标题: 算法与数据结构之java版排序算法 [打印本页]
作者: 专注的一批 时间: 2019-10-23 11:50
标题: 算法与数据结构之java版排序算法
相关术语
稳定性：如果a=b且a在b之前，经排序后a仍在b之前。
时间复杂度：对排序数据的总操作次数。反应排序元素个数n变化时，操作次数呈现什么变化。
空间复杂度：执行算法时所需的存储空间大小。
一、冒泡排序（Bubble Sort）
重复遍历要排序的数列，依次比较相邻的两个元素，调整这两个元素的顺序，直到数列整体有序。
时间复杂度：O(n2)，空间复杂度：O(1)，稳定性：稳定
public void bubble(int arr[]) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int swap = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = swap;
}
}
}
}
二、快速排序（Quick Sort）
通过一次排序将待排数列分为两个部分，其中一部分元素值比另一部分小，然后继续对这两部分执行上述操作，以达到整体有序。
时间复杂度：O(nlog2n)，空间复杂度：O(nlog2n)，稳定性：不稳定
class Quick {
public void quick(int[] arr, int left, int right) {
if (arr == null) {
return;
}
if (left < right) {
int index = partition(arr, left, right);
quick(arr, left, index - 1);
quick(arr, index + 1, right);
}
}
public int partition(int[] arr, int left, int right) {
// 选最左边的元素为基准pivot
int pivot = left, index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
public void swap(int[] arr, int i, int j) {
int temp = arr;
arr = arr[j];
arr[j] = temp;
}
}
三、选择排序（Selection Sort）
在未排序的数列中找到最小（大）的数，放到已排序数列的最后，直到未排序数列为空。
时间复杂度：O(n2)，空间复杂度：O(1)，稳定性：不稳定
public void select(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int index = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[index] > arr[j]) {
int temp = arr[j];
arr[j] = arr;
arr = temp;
}
}
}
}
四、插入排序（Insertion Sort）
构建有序数列，对于无序数列，从有序数列后面遍历，找到合适的位置插入。
时间复杂度：O(n2)，空间复杂度：O(1)，稳定性：稳定
public void insert(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) {
int preIndex = i - 1;
int current = arr;
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
}
五、希尔排序（Shell Sort）
又称缩小增量排序，选取increment作为间隔分为increment个子序列，每个子序列使用直接插入排序，然后缩小increment直到increment=1。
时间复杂度：O(n1.3)，空间复杂度：O(1)，稳定性：不稳定
public void shellSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int increment = arr.length;
do {
increment = increment / 3 + 1;
for (int i = increment; i < arr.length; i++) {
int preIndex = i - increment;
int current = arr;
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + increment] = arr[preIndex];
preIndex -= increment;
}
arr[preIndex + increment] = current;
}
} while (increment > 1);
}
increment的选取规则
increment = n / 2向下取整，但是奇数位置和偶数位置在increment=1时才比较，效率低
increment = n / 3向下取整 + 1
六、堆排序（Heap Sort）
将无序数列转化为最大（小）堆，然后堆顶元素与无序区外汇返佣http://www.fx61.com/最后一个元素替换，重构无序数列为最大（大）堆，继续替换重构直到无序区元素为一个。
时间复杂度：O(nlog2n)，空间复杂度：O(1)，稳定性：不稳定
public void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 第一步：将数组变为最大堆。从下到上，从右到左构建最大堆
// 最后一个非叶子节点开始构建堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
maxHeap(arr, arr.length - 1, i);
}
// 第二步：堆顶元素与最后一个元素交换，然后对前n-1个元素进行最大堆化
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
maxHeap(arr, i - 1, 0);
}
}
public void maxHeap(int[] arr, int size, int index) {
int left = index * 2 + 1;
int right = left + 1;
int max = index;
if (left > size) {
return;
}
if (arr[left] > arr[max]) {
max = left;
}
if (right <= size && arr[right] > arr[max]) {
max = right;
}
if (max != index) {
swap(arr, max, index);
maxHeap(arr, size, max);
}
}
public void swap(int[] arr, int i, int j) {
int temp = arr;
arr = arr[j];
arr[j] = temp;
}
七、计数排序（Counting Sort）
无序数列都为整数，且知道最大数为k。可以创建k+1大小的数组，遍历无序数列，将其值出现的次数记载k+1数组对应的下标中。
时间复杂度：O(n+k)，空间复杂度：O(n+k)，稳定性：稳定。
// arr数组中的最大值
public void countSort(int[] arr, int max) {
int[] bucket = new int[max + 1];
for (int i = 0; i < arr.length; i++) {
bucket[arr]++;
}
int index = 0;
for (int j = 0; j < bucket.length; j++) {
int len = bucket[j];
while (len-- > 0) {
arr[index++] = j;
}
}
}
八、桶排序（Bucket Sort）
基于计数排序，按照映射关系f，将待排数列元素放到k个桶的指定位置，桶内排序可使用快排等，然后依次将桶内数据输出。
时间复杂度：O(n+k)空间复杂度：O(n+k)稳定性：稳定
适用于数据均匀分布在某一范围。
public void bucketSort(int[] arr) {
// 找出最大值和最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr);
min = Math.min(min, arr);
}
int bucketSize = (max - min) / arr.length + 1;
List<List<Integer>> bucket = new ArrayList<>(bucketSize);
// 初始化桶
for (int i = 0; i < bucketSize; i++) {
bucket.add(new ArrayList<>());
}
// 将数据放入对应桶中
for (int i = 0; i < arr.length; i++) {
int num = (arr - min) / arr.length;
bucket.get(num).add(arr);
}
// 将各个桶进行排序
int index = 0;
for (int i = 0; i < bucketSize; i++) {
if (!bucket.get(i).isEmpty()) {
Collections.sort(bucket.get(i));
for (int item : bucket.get(i)) {
arr[index++] = item;
}
}
}
}
九、基数排序（Radix Sort）
对每个数从最低位开始排序，将其放入【0-9】桶中，直至排到最高位。
时间复杂度：O(n*k)，空间复杂度：O(n+k)，稳定性：稳定。
步骤：
找出数组中最大数，并判断其位数。
创建二维数组，保存从最低位到最高位的排序中间结果。
针对每一趟排序，进行元素的分配和收集。
class RadixSort {
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxDigit = getMaxDigit(arr);
return radixSort(arr, maxDigit);
}
/**
* 获取最高位数
*/
private int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLenght(maxValue);
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
protected int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
private int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
int[][] counter = new int[mod * 2][0];
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}
return arr;
}
/**
* 自动扩容，并保存数据
*
* @param arr
* @param value
*/
private int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}
十、归并排序（Merge Sort）
将序列一直对半分，直到每个子序列只有一个元素，然后在合并。
时间复杂度：O(nlog2n)，空间复杂度：O(n)，稳定性：稳定。
采用分而治之思想。
public void mergeSort(int[] arr, int start, int end) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
merge(arr, start, mid, end);
}
private void merge(int[] arr, int start, int mid, int end) {
int[] tmp = new int[end - start + 1];
int left = start, right = mid + 1, tmpIndex = 0;
while (left <= mid && right <= end) {
if (arr[left] < arr[right]) {
tmp[tmpIndex++] = arr[left++];
} else {
tmp[tmpIndex++] = arr[right++];
}
}
while (left <= mid) {
tmp[tmpIndex++] = arr[left++];
}
while (right <= end) {
tmp[tmpIndex++] = arr[right++];
}
for (int i = 0; i < tmp.length; i++) {
arr[start + i] = tmp;
}
}
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |