//冒泡排序,将最大数沉到底部
private 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;
}
}
}
}
//选择排序，将最小数放到顶部
private static 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;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
//插入排序，对已排序数组进行插入
private static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int preIndex = i - 1;
int current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
}
//希尔排序（缩小增量排序），插入排序的升级版，通过增量分段，不断缩小增量直至1，进行插入排序
private static void shellSort(int[] arr) {
for (int gap = (int) Math.floor(arr.length / 2); gap > 0; gap = (int) Math.floor(gap / 2)) { //增量不断缩小
for (int i = gap; i < arr.length; i++) {
int preIndex = i - gap;
int current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = current;
}
}
}
//归并排序，从最小的两个有序数组不断合成有序数组，最终得到一个有序数组
private static int[] mergeSort(int[] arr) {
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
int[] left = new int[middle];
int[] right = new int[arr.length - middle];
for (int i = 0; i < arr.length; i++) {
if (i < middle) {
left[i] = arr[i];
} else {
right[i - middle] = arr[i];
}
}
return merge(mergeSort(left), mergeSort(right));
}
private static int[] merge(int[] left, int[] right) {
int[] newArr = new int[left.length + right.length];
int leftIndex = 0;
int rightIndex = 0;
int newIndex = 0;
while (left.length > leftIndex && right.length > rightIndex) {
if (left[leftIndex] > right[rightIndex]) {
newArr[newIndex++] = right[rightIndex++];
} else {
newArr[newIndex++] = left[leftIndex++];
}
}
while (left.length > leftIndex) {
newArr[newIndex++] = left[leftIndex++];
}
while (right.length > rightIndex) {
newArr[newIndex++] = right[rightIndex++];
}
return newArr;
}
//快速排序，先分区（找到一个基准，所有小于该基准的数，都在其前面，大于的在其后面),递归排序
private static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivot = partion(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
}
private static int partion(int[] arr, int left, int right) {
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//堆排序，构造大顶堆(父节点比子节点大)，将第一个元素和最后一个元素交换，再调整第一个到倒数第二个元素成新的大顶堆，再交换，依次进行
private static void heapSort(int[] arr) {
for (int i = arr.length / 2 - 1; i >= 0; i--) {
herivy(arr, i, arr.length);
}
for (int i = arr.length - 1; i >= 0; i--) {
swap(arr, 0, i);
herivy(arr, 0, i);
}
}
private static void herivy(int[] arr, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int bigest = i;
if (left < len && arr[left] > arr[bigest]) {
bigest = left;
}
if (right < len && arr[right] > arr[bigest]) {
bigest = right;
}
if (i != bigest) {
swap(arr, i, bigest);
herivy(arr, bigest, len);
}
}
//计数排序，找到数组中的最大数和最小数，构造最大数数量的桶，填充对应的桶，按桶的顺序依次拿出数
private static void countingSort(int[] arr) {
int min = arr[0];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
}
if (arr[i] > max) {
max = arr[i];
}
}
int[] countArr = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
countArr[arr[i] - min]++;
}
int index = 0;
for (int i = 0; i < countArr.length; i++) {
while (countArr[i] > 0) {
arr[index] = i + min;
index++;
countArr[i]--;
}
}
}
//桶排序(需要满足均匀分布，不然桶的数量会暴增)，计数排序的升级版，通过数组里的最大最小值和桶大小，构造一定数量的桶，按照均匀分布将数放到桶里，然后对桶里数组排序，最后拿出数组
private static void bucketSort(int[] arr) {
if (arr.length < 0) {
return;
}
int bucketSize = 5;
int min = arr[0];
int max = arr[0];
for (int i = 0; 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;
ArrayList<Integer>[] bucketArr = new ArrayList[bucketCount];
for (int i = 0; i < arr.length; i++) {
int count = (arr[i] - min) / bucketSize;
if (bucketArr[count] == null) {
bucketArr[count] = new ArrayList<>();
}
bucketArr[count].add(arr[i]);
}
int index = 0;
for (int i = 0; i < bucketCount; i++) {
if (bucketArr[i] != null) {
if (bucketArr[i].size() > 1) {
Collections.sort(bucketArr[i]);
}
for (int j = 0; j < bucketArr[i].size(); j++) {
arr[index] = bucketArr[i].get(j);
index++;
}
}
}
}
//基数排序，获取最大位数，然后优先排序低位，再排序高位，利用的思想是桶排序（好像不支持负数参与排序，需要把数组改为LinkHashMap存储）
private static void radixSort(int[] arr) {
int maxDigit = findMaxDigit(arr);
int dev = 1;
int mod = 10;
for (int i = 0; i < maxDigit; i++) {
int maxCurrentDigit = arr[0] % mod / dev;
for (int j = 0; j < arr.length; j++) {
int currentDigit = arr[j] % mod / dev;
if (currentDigit > maxCurrentDigit) {
maxCurrentDigit = currentDigit;
}
}
ArrayList<Integer>[] bucketArr = new ArrayList[maxCurrentDigit + 1];
for (int j = 0; j < arr.length; j++) {
int currentDigit = arr[j] % mod / dev;
if (bucketArr[currentDigit] == null) {
bucketArr[currentDigit] = new ArrayList<>();
}
bucketArr[currentDigit].add(arr[j]);
}
int index = 0;
for (int j = 0; j < bucketArr.length; j++) {
if (bucketArr[j] != null) {
for (int d = 0; d < bucketArr[j].size(); d++) {
arr[index] = bucketArr[j].get(d);
index++;
}
}
}
dev *= 10;
mod *= 10;
}
}
private static int findMaxDigit(int[] arr) {
if (arr.length < 0) {
return 0;
}
int absMax = arr[0];
for (int i = 0; i < arr.length; i++) {
if (Math.abs(arr[i]) > absMax) {
absMax = Math.abs(arr[i]);
}
}
int digit = 0;
while (absMax > 0) {
absMax /= 10;
digit++;
}
return digit;
}十大排序算法
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
