Java의 다양한 정렬 알고리즘 구현 코드 예
- 黄舟원래의
- 2017-10-20 09:54:431572검색
이 글은 주로 Java로 구현된 다양한 정렬 알고리즘의 코드 예제를 소개합니다. 비교적 포괄적이며 개인적인 테스트에 사용할 수 있는 단점이 있으면 지적해 주시기 바랍니다.
반 삽입 정렬
반 삽입 정렬은 직접 삽입 정렬을 간단하게 개선한 것입니다. 여기서 소개하는 반 삽입은 실제로 연속적으로 반을 접어서 i번째 요소의 삽입 위치를 빠르게 결정하는 것입니다. 이것은 실제로는 반 탐색 알고리즘입니다. Java Arrays 클래스의 binarySearch() 메소드는 이진 검색의 구현입니다. 이는 배열이 이미 정렬된 상태인 경우 지정된 배열에서 지정된 요소를 찾는 데 사용됩니다. 효과는 직접 삽입 정렬과 동일하지만 조금 더 빠릅니다. 왜냐하면
반 삽입 정렬을 사용하면 i번째 요소의 삽입 위치를 더 빠르게 결정할 수 있기 때문입니다
코드:
package interview;
/**
* @author Administrator
* 折半插入排序
*/
public class BinaryInsertSort {
public static void binaryInsertSort(DataWrap[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
for (int i = 1; i < arrayLength; i++) {
DataWrap temp = data[i];
int low = 0;
int high = i - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (temp.compareTo(data[mid]) > 0) {
low = mid + 1;
} else {
high = mid - 1;
}
}
for (int j = i; j > low; j--) {
data[j] = data[j - 1];
}
data[low] = temp;
System.out.println(java.util.Arrays.toString(data));
}
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(-30, ""), new DataWrap(-49, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "")};
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
binaryInsertSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}결과:
排序之前： [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 开始排序 [-16, 9, 21*, 23, -30, -49, 21, 30*, 30] [-16, 9, 21*, 23, -30, -49, 21, 30*, 30] [-16, 9, 21*, 23, -30, -49, 21, 30*, 30] [-30, -16, 9, 21*, 23, -49, 21, 30*, 30] [-49, -30, -16, 9, 21*, 23, 21, 30*, 30] [-49, -30, -16, 9, 21, 21*, 23, 30*, 30] [-49, -30, -16, 9, 21, 21*, 23, 30*, 30] [-49, -30, -16, 9, 21, 21*, 23, 30, 30*] 排序之后： [-49, -30, -16, 9, 21, 21*, 23, 30, 30*]
버블 정렬
코드:
package interview;
/**
* @author Administrator
* 冒泡排序
*/
public class BubbleSort {
public static void bubbleSort(DataWrap[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
for (int i = 0; i < arrayLength - 1; i++) {
boolean flag = false;
for (int j = 0; j < arrayLength - 1 - i; j++) {
if (data[j].compareTo(data[j + 1]) > 0) {
DataWrap temp = data[j + 1];
data[j + 1] = data[j];
data[j] = temp;
flag = true;
}
}
System.out.println(java.util.Arrays.toString(data));
if (!flag)
break;
}
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(-30, ""), new DataWrap(-49, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "")};
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
bubbleSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}실행 결과:
排序之前： [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 开始排序 [-16, 9, 21*, -30, -49, 21, 23, 30*, 30] [-16, 9, -30, -49, 21*, 21, 23, 30*, 30] [-16, -30, -49, 9, 21*, 21, 23, 30*, 30] [-30, -49, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] 排序之后： [-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
버킷 정렬
알고리즘의 시간 효율성: 극도의 시간 효율성 높음, 두 번의 순회만 필요합니다. 알고리즘의 공간 효율성: 공간 오버헤드가 크고 알고리즘의 안정성: 안정적입니다.
package interview;
import java.util.Arrays;
/**
* @author Administrator
* 桶式排序
*/
public class BucketSort {
public static void bucketSort(DataWrap[] data, int min, int max) {
System.out.println("开始排序");
int arrayLength = data.length;
DataWrap[] temp = new DataWrap[arrayLength];
int[] buckets = new int[max - min];
for (int i = 0; i < arrayLength; i++) {
buckets[data[i].data - min]++;
}
System.out.println(Arrays.toString(buckets));
for (int i = 1; i < max - min; i++) {
buckets[i] = buckets[i] + buckets[i - 1];
}
System.out.println(Arrays.toString(buckets));
System.arraycopy(data, 0, temp, 0, arrayLength);
for (int k = arrayLength - 1; k >= 0; k--) {
data[--buckets[temp[k].data - min]] = temp[k];
}
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9, ""), new DataWrap(5, ""),
new DataWrap(-1, ""), new DataWrap(8, ""),
new DataWrap(5, "*"), new DataWrap(7, ""),
new DataWrap(3, ""), new DataWrap(-3, ""),
new DataWrap(1, ""),new DataWrap(3, "*")};
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
bucketSort(data, -3, 10);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
} 코드:
排序之前：
[9, 5, -1, 8, 5*, 7, 3, -3, 1, 3*]
开始排序
[1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 1, 1, 1]
[1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 8, 9, 10]
排序之后：
[-3, -1, 1, 3, 3*, 5, 5*, 7, 8, 9]
결과:
package interview;
/**
* @author Administrator
* 堆排序
*/
public class HeapSort {
public static void heapSort(DataWrap[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
// 循环建堆
for (int i = 0; i < arrayLength - 1; i++) {
// 建堆
builMaxdHeap(data, arrayLength - 1 - i);
// 交换堆顶和最后一个元素
swap(data, 0, arrayLength - 1 - i);
System.out.println(java.util.Arrays.toString(data));
}
}
// 对data数组从0到lastIndex建大顶堆
private static void builMaxdHeap(DataWrap[] data, int lastIndex) {
// 从lastIndex处节点（最后一个节点）的父节点开始
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
// k保存当前正在判断的节点
int k = i;
// 如果当前k节点的子节点存在
while (k * 2 + 1 <= lastIndex) {
// k节点的左子节点的索引
int biggerIndex = 2 * k + 1;
// 如果biggerIndex小于lastIndex，即biggerIndex +1
// 代表k节点的右子节点存在
if (biggerIndex < lastIndex) {
// 如果右子节点的值较大
if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) {
// biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
// 如果k节点的值小于其较大子节点的值
if (data[k].compareTo(data[biggerIndex]) < 0) {
// 交换它们
swap(data, k, biggerIndex);
// 将biggerIndex赋给k，开始while循环的下一次循环
// 重新保证k节点的值大于其左、右节点的值
k = biggerIndex;
} else {
break;
}
}
}
}
// 交换data数组中i、j两个索引处的元素
private static void swap(DataWrap[] data, int i, int j) {
DataWrap temp = data[i];
data[i] = data[j];
data[j] = temp;
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(-30, ""), new DataWrap(-49, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "")};
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
heapSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}직접 삽입 정렬
排序之前： [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 开始排序 [-16, 30, 21*, 23, -30, -49, 21, 9, 30*] [-16, 23, 21*, 9, -30, -49, 21, 30, 30*] [21, 9, 21*, -16, -30, -49, 23, 30, 30*] [-49, 9, 21*, -16, -30, 21, 23, 30, 30*] [-30, 9, -49, -16, 21*, 21, 23, 30, 30*] [-30, -16, -49, 9, 21*, 21, 23, 30, 30*] [-49, -30, -16, 9, 21*, 21, 23, 30, 30*] [-49, -30, -16, 9, 21*, 21, 23, 30, 30*] 排序之后： [-49, -30, -16, 9, 21*, 21, 23, 30, 30*]결과
package interview;
public class InsertSort {
public static void insertSort(DataWrap[] data){
System.out.println("开始排序");
int arrayLength = data.length;
for(int i = 1;i < arrayLength;i++){
DataWrap temp = data[i];
if(data[i].compareTo(data[i-1]) < 0){
int j = i -1;
for(;j >= 0 && data[j].compareTo(temp) > 0;j--){
data[j +1] = data[j];
}
data[j + 1] = temp;
}
System.out.println(java.util.Arrays.toString(data));
}
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(-30, ""), new DataWrap(-49, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "")};
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
insertSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
merge()에는 n번의 비교가 필요하며 더 나쁜 경우에는 원래 시퀀스와 동일한 크기의 보조 시퀀스가 필요합니다. 알고리즘의 안정성: 안정적
코드:
排序之前：
[9, -16, 21*, 23, -30, -49, 21, 30*, 30]
开始排序
[-16, 9, 21*, 23, -30, -49, 21, 30*, 30]
[-16, 9, 21*, 23, -30, -49, 21, 30*, 30]
[-16, 9, 21*, 23, -30, -49, 21, 30*, 30]
[-30, -16, 9, 21*, 23, -49, 21, 30*, 30]
[-49, -30, -16, 9, 21*, 23, 21, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
排序之后：
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
결과:
package interview;
/**
* @author Administrator
* 归并排序
*/
public class MergeSort {
public static void mergeSort(DataWrap[] data) {
// 归并排序
sort(data, 0, data.length - 1);
}
// 将索引从left到right范围的数组元素进行归并排序
private static void sort(DataWrap[] data, int left, int right) {
if(left < right){
//找出中间索引
int center = (left + right)/2;
sort(data,left,center);
sort(data,center+1,right);
//合并
merge(data,left,center,right);
}
}
// 将两个数组进行归并，归并前两个数组已经有序，归并后依然有序
private static void merge(DataWrap[] data, int left, int center, int right) {
DataWrap[] tempArr = new DataWrap[data.length];
int mid = center + 1;
int third = left;
int temp = left;
while (left <= center && mid <= right) {
if (data[left].compareTo(data[mid]) <= 0) {
tempArr[third++] = data[left++];
} else {
tempArr[third++] = data[mid++];
}
}
while (mid <= right) {
tempArr[third++] = data[mid++];
}
while (left <= center) {
tempArr[third++] = data[left++];
}
while (temp <= right) {
data[temp] = tempArr[temp++];
}
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(-30, ""), new DataWrap(-49, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "") };
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
mergeSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
} 기수 정렬은 더 이상 일반적인 정렬 방법이 아닙니다. 신청 한 정렬 방법 중 기수 정렬은 다른 정렬 방법에 의존해야 합니다.
기수 정렬의 일반적인 개념은 정렬할 데이터를 여러 키워드로 분할하여 정렬하는 것입니다. 즉, 기수 정렬의 본질은 다중 키워드 정렬입니다.
최고 비트 우선 방식 MSD최하위 비트 우선 방식 LSD
MSD 방식과 LSD 방식을 비교하면 일반적으로 LSD 방식이 더 좋습니다. MSD 방법 LSD 방법은 처음부터 끝까지 여러 번의 할당과 수집을 수행하고 실행 횟수는 키 값을 구성하는 구성 요소 수에 따라 달라지지만 MSD 방법은 독립적인 정렬을 처리해야 하기 때문에 간단합니다. 각 시퀀스와 하위 시퀀스의 일부는 복잡할 수 있습니다.
코드:
排序之前：
[9, -16, 21*, 23, -30, -49, 21, 30*, 30]
排序之后：
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
결과
package interview;
import java.util.Arrays;
/**
* @author Administrator
* 基数排序
*/
public class MultiKeyRadixSort {
public static void radixSort(int[] data, int radix, int d) {
System.out.println("开始排序：");
int arrayLength = data.length;
int[] temp = new int[arrayLength];
int[] buckets = new int[radix];
for (int i = 0, rate = 1; i < d; i++) {
// 重置count数组，开始统计第二个关键字
Arrays.fill(buckets, 0);
// 当data数组的元素复制到temp数组中进行缓存
System.arraycopy(data, 0, temp, 0, arrayLength);
for (int j = 0; j < arrayLength; j++) {
int subKey = (temp[j] / rate) % radix;
buckets[subKey]++;
}
for (int j = 1; j < radix; j++) {
buckets[j] = buckets[j] + buckets[j - 1];
}
for (int m = arrayLength - 1; m >= 0; m--) {
int subKey = (temp[m] / rate) % radix;
data[--buckets[subKey]] = temp[m];
}
System.out.println("对" + rate + "位上子关键字排序："
+ java.util.Arrays.toString(data));
rate *= radix;
}
}
public static void main(String[] args) {
int[] data = { 1100, 192, 221, 12, 13 };
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
radixSort(data, 10, 4);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}코드:
排序之前： [1100, 192, 221, 12, 13] 开始排序： 对1位上子关键字排序：[1100, 221, 192, 12, 13] 对10位上子关键字排序：[1100, 12, 13, 221, 192] 对100位上子关键字排序：[12, 13, 1100, 192, 221] 对1000位上子关键字排序：[12, 13, 192, 221, 1100] 排序之后： [12, 13, 192, 221, 1100]
Resultspackage interview;
/**
* @author Administrator
* 快速排序
*/
public class QuickSort {
private static void swap(DataWrap[] data, int i, int j) {
DataWrap temp = data[i];
data[i] = data[j];
data[j] = temp;
}
private static void subSort(DataWrap[] data, int start, int end) {
if (start < end) {
DataWrap base = data[start];
int i = start;
int j = end + 1;
while (true) {
while (i < end && data[++i].compareTo(base) <= 0)
;
while (j > start && data[--j].compareTo(base) >= 0)
;
if (i < j) {
swap(data, i, j);
} else {
break;
}
}
swap(data, start, j);
subSort(data, start, j - 1);
subSort(data, j + 1, end);
}
}
public static void quickSort(DataWrap[] data){
subSort(data,0,data.length-1);
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(-30, ""), new DataWrap(-49, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "") };
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
quickSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
코드:
排序之前： [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 排序之后： [-49, -30, -16, 9, 21, 21*, 23, 30*, 30]
package interview;
/**
* @author Administrator
* 直接选择排序
*/
public class SelectSort {
public static void selectSort(DataWrap[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
for (int i = 0; i < arrayLength - 1; i++) {
for (int j = i + 1; j < arrayLength; j++) {
if (data[i].compareTo(data[j]) > 0) {
DataWrap temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
System.out.println(java.util.Arrays.toString(data));
}
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(-30, ""), new DataWrap(-49, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "") };
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
selectSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}힐 정렬
코드:
排序之前： [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 开始排序 [-49, 9, 21*, 23, -16, -30, 21, 30*, 30] [-49, -30, 21*, 23, 9, -16, 21, 30*, 30] [-49, -30, -16, 23, 21*, 9, 21, 30*, 30] [-49, -30, -16, 9, 23, 21*, 21, 30*, 30] [-49, -30, -16, 9, 21*, 23, 21, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] 排序之后： [-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
결과:package interview;
/**
* @author Administrator
* Shell排序
*/
public class ShellSort {
public static void ShellSort(DataWrap[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
int h = 1;
/**
* 将数组分割成若干个子序列
*/
while (h <= arrayLength / 3) {
h = h * 3 + 1;
System.out.println("h的结果：" + h);
}
while (h > 0) {
System.out.println("===h的值：" + h + "===");
/**
* 将分成的若干子序列进行直接插入排序
*/
for (int i = h; i < arrayLength; i++) {
DataWrap temp = data[i];
if (data[i].compareTo(data[i - h]) < 0) {
int j = i - h;
for (; j >= 0 && data[j].compareTo(temp) > 0; j -= h) {
data[j + h] = data[j];
}
data[j + h] = temp;
}
System.out.println(java.util.Arrays.toString(data));
}
h = (h - 1) / 3;
}
}
public static void main(String[] args) {
DataWrap[] data = {
new DataWrap(9, ""), new DataWrap(-16, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(-30, ""), new DataWrap(-49, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "")};
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
ShellSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
排序之前： [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 开始排序 h的结果：4 ===h的值：4=== [-30, -16, 21*, 23, 9, -49, 21, 30*, 30] [-30, -49, 21*, 23, 9, -16, 21, 30*, 30] [-30, -49, 21*, 23, 9, -16, 21, 30*, 30] [-30, -49, 21*, 23, 9, -16, 21, 30*, 30] [-30, -49, 21*, 23, 9, -16, 21, 30*, 30] ===h的值：1=== [-49, -30, 21*, 23, 9, -16, 21, 30*, 30] [-49, -30, 21*, 23, 9, -16, 21, 30*, 30] [-49, -30, 21*, 23, 9, -16, 21, 30*, 30] [-49, -30, 9, 21*, 23, -16, 21, 30*, 30] [-49, -30, -16, 9, 21*, 23, 21, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] 排序之后： [-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
위 내용은 Java의 다양한 정렬 알고리즘 구현 코드 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!