题解 | #排序#（九大排序算法Java实现）
排序
https://www.nowcoder.com/practice/2baf799ea0594abd974d37139de27896
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
// write code here
//bubbleSort(arr);
//selectionSort(arr);
//heapSort(arr);
// insertSort(arr);
//shellSort(arr);
//mergeSort(arr);
//mergeSort1(arr);
//quickSort(arr);
//countSort(arr);
bucketSort(arr, 100);
return arr;
}
// 冒泡排序
private void bubbleSort(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
boolean flag = false;
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
flag = true;
}
}
if (!flag)break;
}
}
// 选择排序
private void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (i == minIndex)continue;
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
// 堆排序
private void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 将堆顶元素与堆尾元素交换，并且重新调整
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
private void heapify(int[] arr, int n, int i) {
int largest = i; // 初始化最大元素为根节点
int left = i * 2 + 1;
int right = left + 1;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (i != largest) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
// 插入排序
private void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int idx = i - 1;
int insert = arr[i];
while (idx >= 0 && insert < arr[idx]) {
arr[idx + 1] = arr[idx];
idx--;
}
arr[idx + 1] = insert;
}
}
// 希尔排序
private void shellSort(int[] arr) {
int gap = arr.length >> 2;
while (gap > 0) {
for (int i = gap; i < arr.length; 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;
}
gap /= 2;
}
}
// 归并排序
// 自顶至下的递归版本
private void mergeSort(int[] arr) {
if (arr == null || arr.length < 2)return;
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
}
private void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left >= right)return; // 只有一个元素时不用排序
int mid = (left + right) >>> 1; // 除2获得中间索引
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
if (arr[mid] <= arr[mid + 1])
return; // 当左侧子数组的最大值小于等于右侧子数组的最小值时，不需要合并
merge(arr, left, mid, right, temp);
}
private void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left, j = mid + 1, 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[t++] = arr[i++];
}
while (j <= right) {
temp[t++] = arr[j++];
}
// 注意从left开始
System.arraycopy(temp, 0, arr, left, t);
}
// 自底向上的迭代版本
private void mergeSort1(int[] arr) {
int n = arr.length;
int[] temp = new int[n];
for (int width = 1; width < n; width *= 2) {
for (int left = 0; left < n; left += width * 2) {
int right = Math.min(left + width * 2 - 1, n - 1);
int mid = Math.min(left + width - 1, n - 1);
merge(arr, left, mid, right, temp);
}
}
}
// 快速排序
private void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pv = partition(arr, left, right);
quickSort(arr, left, pv - 1);
quickSort(arr, pv + 1, right);
}
}
private int partition(int[] arr, int left, int right) {
// 随机基准点
int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
swap(arr, left, idx);
int pv = arr[left];
int low = left + 1, high = right;
// 处理重复元素
while (low <= high) {
while (low <= high && arr[high] > pv) {
high--;
}
while (low <= high && arr[low] < pv) {
low++;
}
if (low <= high) {
swap(arr, low, high);
low++;
high--;
}
}
swap(arr, left, high);
return high;
}
private void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// 计数排序不适合本题，因为数据范围太大
// private void countSort(int[] arr){
// int max = arr[0], min = arr[0];
// for(int i = 0; i < arr.length; i++){
// if(arr[i] > max) max = arr[i];
// if(arr[i] < min) min = arr[i];
// }
// int[] count = new int[max - min + 1];
// for(int val : arr){
// count[val - min]++;
// }
// int k = 0;
// for(int i = 0; i < count.length; i++){
// while(count[i] > 0){
// arr[k++] = i + min;
// count[i]--;
// }
// }
// }
// 桶排序，本题设置桶大小100可以通过
private void bucketSort(int[] arr, int size) {
int max = arr[0], min = arr[0];
for(int i = 0; i < arr.length; i++){
if(arr[i] > max) max = arr[i];
if(arr[i] < min) min = arr[i];
}
// 计算桶的数量
int count = (max - min) / size + 1;
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(count);
// 初始化桶
for(int i = 0; i < count; i++){
buckets.add(new ArrayList<>());
}
// 将数据放入对应的桶中
for(int val : arr){
// 计算放入哪个桶
int idx = (val - min) / size;
buckets.get(idx).add(val);
}
// 对每个桶进行排序
for(int i = 0; i < count; i++){
Collections.sort(buckets.get(i));
}
// 取出每个桶中的元素
int k = 0;
for(int i = 0; i < count; i++){
for(int j = 0; j < buckets.get(i).size(); j++){
arr[k++] = buckets.get(i).get(j);
}
}
}
}
#题解分享#
投递思朗科技等公司10个岗位