以下排序算法均按升序处理。
1.冒泡排序
算法原理：依次比较两个数的大小，如果左边的数大于右边的数，就交换两者的位置，当第一轮交换结束后，最后一个数肯定是整个数组中最大的那个数，因此下一轮比较的时候这个数就不需要比较了。
优化：按照上面的写有一个弊端，当数组初始状态就是部分或者完全升序，还是需要全部比较，这耗费很多时间，因此可以标记哪个位置以后是完全有序，就比较这个位置之前的位置就可以了。
冒泡排序是一个稳定的算法，是因为如果遇到相同的数，排序后不会改变相同的数它们彼此的相对位置。
时间复杂度：O(n²)
空间复杂度：O(n)
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public class BubbleSort {
public static void sort(int[] nums){
for (int end = nums.length - 1; end > 0; end--) {
int index = 0;
for (int i = 1; i <= end; i++) {
if(nums[i] < nums[i - 1]){
int temp = nums[i];
nums[i] = nums[i - 1];
nums[i - 1] = temp;
index = i;
}
}
end = index;
}
}
public static void main(String[] args) {
int[] nums = {5,8,7,4,6,5,3,9,8,10,0};
BubbleSort.sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+"_");
}
}
}
|
2.选择排序
算法原理：先将所有数进行比较，找出最大的那个数，然后让这个数与最后一个元素交换位置，这时最大的数就在最后面了，接着缩小范围再进行选择比较。
选择排序也是一个稳定的算法。
时间复杂度：O(n²)
空间复杂度：O(1)
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public class SelectionSort {
public static void sort(int[] nums){
for (int end = nums.length - 1; end > 0; end--) {
int max = 0;
for (int i = 1; i <= end; i++) {
if(nums[max] <= nums[i]){
max = i;
}
}
int temp = nums[max];
nums[max] = nums[end];
nums[end] = temp;
}
}
public static void main(String[] args) {
int[] nums = {5,8,7,4,6,5,3,9,8,10,0};
SelectionSort.sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+"_");
}
}
}
|
3.堆排序
堆排序可以认为是对选择排序的一种优化。
时间复杂度：O(nlogn)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| public class HeapSort {
private int heapSize;
private int[] nums;
public void sort(int[] nums){
this.nums = nums;
heapSize = nums.length;
for(int i = (heapSize >> 1) - 1; i >= 0; i--){
siftDown(i);
}
while(heapSize > 1){
int top = nums[0];
nums[0] = nums[heapSize - 1];
nums[heapSize - 1] = top;
heapSize--;
siftDown(0);
}
}
private void siftDown(int index){
int element = nums[index];
int half = heapSize >> 1;
while(index < half){
int leftIndex = (index << 1) + 1;
int leftChild = nums[leftIndex];
int rightIndex = leftIndex + 1;
if(rightIndex < heapSize && nums[rightIndex] > leftChild){
leftIndex = rightIndex;
leftChild = nums[rightIndex];
}
if(element >= leftChild){
break;
}
nums[index] = leftChild;
index = leftIndex;
}
nums[index] = element;
}
public static void main(String[] args) {
int[] nums = {5,8,7,4,6,5,3,9,8,10,0};
HeapSort heap = new HeapSort();
heap.sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+"_");
}
}
}
|
4.插入排序
算法思想：数组的前一部分是有序的，后一部分是无序的，将后面的无序的元素依次插入到前面有序的部分，并保证插入后前一部分仍然是有序的。
假设这个数组是[44,51,61,82,94,96,52,54,71,17,32,60,5]
第一种做法：将52与有序数组依次进行比较，52<96，交换，52<94，交换，…..这样的话假如数组的有序部分都大于52，需要将52交换很多次，最后换到第一个位置，这样效率很低。
第二种做法：我们将【交换】改为【挪动】，首先倒着来，依次比较52和她们的大小关系，然后找出那个小于52的索引前面的索引，就是52要插入的位置，然后将这个位置到52位置的所有元素向右挪动一个位置，然后直接将52赋值到这个索引处。如果有序数组是倒序，也需要比较很多次才能找到这个索引。
第三种做法：利用二分查找的原理，二分地找出第一个大于52的数的索引，然后将它们挪动，再将52赋值到这个索引处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| public class InsertSort {
private int[] nums;
public void sort(int[] nums){
this.nums = nums;
for (int i = 1; i < nums.length; i++) {
int index = search(i);
int element = nums[i];
for (int j = i; j > index; j--) {
nums[j] = nums[j - 1];
}
nums[index] = element;
}
}
private int search(int index){
int begin = 0;
int end = index;
while(begin < end){
int mid = (begin + end) >> 1;
if(nums[index] < nums[mid]){
end = mid;
}else{
begin = mid + 1;
}
}
return begin;
}
public static void main(String[] args) {
int[] nums = {5,8,7,4,6,5,3,9,8,10,0};
InsertSort insertSort = new InsertSort();
insertSort.sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+"_");
}
}
}
|
5.归并排序
算法思想：将一个大数组分为两个小数组，在递归地将这两个小数组分为4个小数组，一直递归，终止条件是每个数组都只有一个元素，每个数组一定是一个有序数组，因为只有一个元素肯定是有序的啦，然后两两合并，合并完的仍然是有序数组才可以，最终合并成一个有序数组。
时间复杂度：O(nlogn)
空间复杂度：O(n)
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| public class MergeSort {
private int[] leftArray;
private int[] nums;
public void sort(int[] nums){
this.nums = nums;
leftArray = new int[nums.length >> 1];
sort(0,nums.length);
}
private void sort(int begin,int end){
if(end - begin < 2) return;
int mid = (begin + end) >> 1;
sort(begin,mid);
sort(mid,end);
merge(begin,mid,end);
}
private void merge(int begin, int mid, int end) {
int point = begin;
int right = mid;
for (int i = 0; i < mid - begin; i++) {
leftArray[i] = nums[begin + i];
}
int left = 0;
while (left < mid - begin){
if(right >= end || leftArray[left] <= nums[right]){
nums[point++] = leftArray[left++];
}else{
nums[point++] = nums[right++];
}
}
}
public static void main(String[] args) {
int[] nums = {5,8,7,4,6,5,3,9,8,10,0};
MergeSort mergeSort = new MergeSort();
mergeSort.sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+"_");
}
}
}
|
6.快速排序
算法思想：先选择一个轴点元素，比轴点元素大的元素放在轴点元素的右边，比轴点元素小的元素放在它的左边，然后再将轴点元素两遍的序列递归进行这个步骤，逐渐将每个元素都变成轴点元素。所以递归终止条件就是每个元素都变成了轴点元素。这样所有元素都是有序了。
时间复杂度：最好 O(nlogn)，最坏O(n²)
空间复杂度：O(n)
当轴点元素将数组均分或者差不多均分的时候时间复杂度最低，最差的情况是轴点元素一边没有元素，一边是所有元素。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| public class FastSort {
private int[] nums;
public void sort(int[] nums){
this.nums = nums;
sort(0,nums.length);
}
private void sort(int begin,int end){
if(end - begin < 2) return;
int pointIndex = point(begin,end);
sort(begin,pointIndex);
sort(pointIndex,end);
}
private int point(int begin, int end) {
int index = begin + (int) (Math.random() * (end - begin));
int first = nums[begin];
nums[begin] = nums[index];
nums[index] = first;
int element = nums[begin];
end--;
while (begin < end){
while(begin < end){
if(nums[end] > element){
end--;
}else {
nums[begin++] = nums[end];
break;
}
}
while(begin < end){
if(nums[begin] < element){
begin++;
}else{
nums[end--] = nums[begin];
break;
}
}
}
nums[begin] = element;
return begin;
}
public static void main(String[] args) {
int[] nums = {5,8,7,4,6,5,3,9,8,10,0};
FastSort s = new FastSort();
s.sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+"_");
}
}
}
|
这里有一个很巧妙的设计，因为当每次覆盖操作之后，都需要进行反方向的遍历，轮流进行，当遍历的元素不满足与轴点元素的大小关系时，就还是这个方向进行遍历。这里使用了两个while循环，只要一覆盖，就break，换方向，否则不换。
一些转换公式
