慢慢把数据结构和算法补起来吧。。
选择排序
选择排序的核心思想就是先选出来最小的，再从第二个开始选出来最小的，直到全部排序完成。先把第一个数当成最小的，依次和第一个之后的数比较，如果小的话就记下下标，直到选出最小的，和第一个数进行交换。代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13private static void xuanze(int[] a) {
for (int i = 0; i < a.length; i++) {
int min = i;
for (int j = i; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
if (i != min) {
swap(a, i, min);
}
}
}
交换代码：1
2
3
4
5
6
7
8private static void swap(int[] a, int i, int j) {
if (i == j) {
return;
}
a[i] ^= a[j];
a[j] ^= a[i];
a[i] ^= a[j];
}
冒泡排序
冒泡排序的核心思想就是从第一个元素开始，依次和它的下一个元素进行比较，如果比下一个元素的值要大，则交换，直到最大的元素排到最后。这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。
代码如下：1
2
3
4
5
6
7
8
9
10public void sort(int[] a){
int length = a.length;
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a, j, j + 1);
}
}
}
}
插入排序
插入排序的核心思想就是，默认前面的数组是有序的，然后把下个元素插入到应该在的位置。代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public void sort(int[] a){
int j, target = 0;
for (int i = 1; i < a.length; i++) {
j = i;
target = a[i];
while (j > 0 && a[j - 1] > target) {
a[j] = a[j - 1];
j--;
}
a[j] = target;
}
}
public void sort2(int[] a){
for (int i = 1; i < a.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (a[j + 1] < a[j]) {
swap(a, j + 1, j);
} else {
break;
}
}
}
}
快速排序
这个是四个里面最复杂的排序了。当时刚开始看的时候一脸懵逼，后来看到一篇好博客，茅塞顿开：挖坑填数+分治法。
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public static void sort(int[] a , int start , int end){
if(start < end){
int i = start , j = end , x = a[i];
while(i < j){
while ( i < j && a[j] >= x)
j--;
if(i < j)
a[i++] = a[j];
while(i < j && a[i] <= x)
i++;
if(i < j){
a[j--] = a[i];
}
}
a[i] = x;
sort(a , start , i - 1);
sort(a , i + 1 , end);
}
}
