文章目录
冒泡排序插入排序快速排序选择排序归并排序堆排序计数排序
冒泡排序
public class BubbleSort {
public static void bubbleSort(int[] arr
) {
if (arr
== null
|| arr
.length
< 2) {
return;
}
for (int e
= arr
.length
- 1; e
> 0; e
--) {
for (int i
= 0; i
< e
; i
++) {
if (arr
[i
] > arr
[i
+ 1]) {
swap(arr
, i
, i
+ 1);
}
}
}
}
public static void swap(int[] arr
, int i
, int j
) {
int tmp
;
tmp
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = tmp
;
}
public static void main(String
[] args
) {
int[] arr
= { 2, 3, 6, 1, 8, 5, 5, 6, 0 };
bubbleSort(arr
);
for (int i
= 0; i
< arr
.length
; i
++) {
System
.out
.println(arr
[i
]);
}
}
}
插入排序
public class InsertionSort {
public static void insertionSort(int[] arr
) {
if (arr
== null
|| arr
.length
< 2) {
return;
}
for (int i
= 1; i
< arr
.length
; i
++) {
for (int j
= i
- 1; j
>= 0 && arr
[j
] > arr
[j
+ 1]; j
--) {
swap(arr
, j
, j
+ 1);
}
}
}
public static void swap(int[] arr
, int i
, int j
) {
int tmp
;
tmp
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = tmp
;
}
public static void main(String
[] args
) {
int[] arr
= { 2, 3, 6, 1, 8, 5, 5, 6, 0 };
insertionSort(arr
);
for (int i
= 0; i
< arr
.length
; i
++) {
System
.out
.println(arr
[i
]);
}
}
}
快速排序
public class QuickSort {
public static void quickSort(int[] arr
, int l
, int r
) {
if (arr
== null
|| arr
.length
< 2) {
return;
}
if (l
< r
) {
swap(arr
, l
+ (int) Math
.random() * (r
- l
+ 1), r
);
int[] p
= partition(arr
, l
, r
);
quickSort(arr
, l
, p
[0] - 1);
quickSort(arr
, p
[1] + 1, r
);
}
}
public static int[] partition(int[] arr
, int l
, int r
) {
int less
= l
- 1;
int more
= r
;
while (l
< more
) {
if (arr
[l
] < arr
[r
]) {
swap(arr
, ++less
, l
++);
} else if (arr
[l
] > arr
[r
]) {
swap(arr
, --more
, l
);
} else {
l
++;
}
}
swap(arr
, more
, r
);
return new int[] { less
+ 1, more
};
}
public static void swap(int[] arr
, int i
, int j
) {
int tmp
;
tmp
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = tmp
;
}
public static void main(String
[] args
) {
int[] arr
= { 2, 3, 6, 1, 8, 5, 5, 6, 0 };
quickSort(arr
, 0, arr
.length
- 1);
for (int i
= 0; i
< arr
.length
; i
++) {
System
.out
.println(arr
[i
]);
}
}
}
选择排序
public class SelectSort {
public static void selectSort(int[] arr
) {
if (arr
== null
|| arr
.length
< 2) {
return;
}
for (int i
= 0; i
< arr
.length
- 1; i
++) {
int minIndex
= i
;
for (int j
= i
+ 1; j
< arr
.length
; j
++) {
minIndex
= arr
[j
] < arr
[minIndex
] ? j
: minIndex
;
}
swap(arr
, i
, minIndex
);
}
}
public static void swap(int[] arr
, int i
, int j
) {
int tmp
;
tmp
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = tmp
;
}
public static void main(String
[] args
) {
int[] arr
= { 2, 3, 6, 1, 8, 5, 5, 6, 0 };
selectSort(arr
);
for (int i
= 0; i
< arr
.length
; i
++) {
System
.out
.println(arr
[i
]);
}
}
}
归并排序
public class MergeSort {
public static void mergeSort(int[] arr
, int l
, int r
) {
if (arr
== null
|| arr
.length
< 2 || l
== r
) {
return;
}
int mid
= l
+ ((r
- l
) >> 2);
mergeSort(arr
, l
, mid
);
mergeSort(arr
, mid
+ 1, r
);
merge(arr
, l
, mid
, r
);
}
public static void merge(int[] arr
, int l
, int mid
, int r
) {
int[] help
= new int[r
- l
+ 1];
int i
= 0;
int p1
= l
;
int p2
= mid
+ 1;
while (p1
<= mid
&& p2
<= r
) {
help
[i
++] = arr
[p1
] < arr
[p2
] ? arr
[p1
++] : arr
[p2
++];
}
while (p1
<= mid
) {
help
[i
++] = arr
[p1
++];
}
while (p2
<= r
) {
help
[i
++] = arr
[p2
++];
}
for (i
= 0; i
< help
.length
; i
++) {
arr
[l
+ i
] = help
[i
];
}
}
public static void main(String
[] args
) {
int[] arr
= { 9, 3, 1, 1, 8, 5, 5, 6, 0 };
mergeSort(arr
, 0, arr
.length
- 1);
for (int i
= 0; i
< arr
.length
; i
++) {
System
.out
.println(arr
[i
]);
}
}
}
堆排序
public class HeapSort {
public static void heapSort(int[] arr
) {
if (arr
== null
|| arr
.length
< 2) {
return;
}
for (int i
= 0; i
< arr
.length
; i
++) {
heapInsert(arr
, i
);
}
int heapsize
= arr
.length
;
swap(arr
, 0, --heapsize
);
while (heapsize
> 0) {
heapify(arr
, 0, heapsize
);
swap(arr
, 0, --heapsize
);
}
}
public static void heapify(int[] arr
, int index
, int heapsize
) {
int left
= index
* 2 + 1;
while (left
< heapsize
) {
int bigindex
= left
+ 1 < heapsize
&& arr
[left
+ 1] > arr
[left
] ? left
+ 1 : left
;
bigindex
= arr
[bigindex
] > arr
[index
] ? bigindex
: index
;
if (bigindex
== index
) {
break;
}
swap(arr
, bigindex
, index
);
index
= bigindex
;
left
= index
* 2 + 1;
}
}
public static void heapInsert(int[] arr
, int index
) {
while (arr
[index
] > arr
[(index
- 1) / 2]) {
swap(arr
, index
, (index
- 1) / 2);
index
= (index
- 1) / 2;
}
}
public static void swap(int[] arr
, int i
, int j
) {
int tmp
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = tmp
;
}
public static void main(String
[] args
) {
int[] arr
= { 2, 3, 6, 1, 8, 5, 5, 6, 0 };
heapSort(arr
);
for (int i
= 0; i
< arr
.length
; i
++) {
System
.out
.println(arr
[i
]);
}
}
}
计数排序
public class CountSort {
public static void countSort(int[] arr
) {
if (arr
== null
|| arr
.length
< 2) {
return;
}
int max
= Integer
.MIN_VALUE
;
for (int i
= 0; i
< arr
.length
; i
++) {
max
= Math
.max(arr
[i
], max
);
}
int[] bucket
= new int[max
+ 1];
for (int i
= 0; i
< bucket
.length
; i
++) {
bucket
[arr
[i
]]++;
}
int i
= 0;
for (int j
= 0; j
< bucket
.length
; j
++) {
while (bucket
[j
]-- > 0) {
arr
[i
++] = j
;
}
}
}
public static void main(String
[] args
) {
int[] arr
= { 2, 3, 6, 1, 8, 5, 5, 6, 0 };
countSort(arr
);
for (int i
= 0; i
< arr
.length
; i
++) {
System
.out
.println(arr
[i
]);
}
}
}
排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。
