慢慢把数据结构和算法补起来吧。。
选择排序 选择排序的核心思想就是先选出来最小的,再从第二个开始选出来最小的,直到全部排序完成。先把第一个数当成最小的,依次和第一个之后的数比较,如果小的话就记下下标,直到选出最小的,和第一个数进行交换。代码如下:1 2 3 4 5 6 7 8 9 10 11 12 13 private 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 8 private 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 10 public 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 24 public 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 19 public 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); } }