排序算法|Java实现十大经典排序算法--上算法|java

文章目录

- 一、冒泡排序
- 二、选择排序
- 三、插入排序
- 四、希尔排序
- 五、归并排序

一、冒泡排序

文章图片
算法描述：
冒泡排序，就是从头开始不断比较只要不符合大小关系就交换，每次都可以排好一位，算法动图看起来就像是冒泡一样，所以被称为冒泡排序
代码样例：

public static void sort(int[] list) { int n; for (int i = 0; i < list.length; i++) { for (int j = 0; j < list.length-1-i; j++) { //这里为什么时length-1-i? //因为每完整遍历一次j，就有一个数字已经排好了 if (list[j] > list[j + 1]) { n = list[j]; list[j] = list[j + 1]; list[j + 1] = n; } } } }

冒泡排序整体来说没什么难度，也比较好写，不过需要注意的就是第二层循环那里；
二、选择排序

文章图片
算法描述：
首先在列表中寻找最大的元素放到最后或者最前，最小的相反放置，然后找第二小（或者大）的元素，直到最后；
【排序算法|Java实现十大经典排序算法--上】代码样例：

public static void sort(int[] list) { int min; int n; for (int i = 0; i < list.length; i++) { min = i; //从第二个开始比较到最后 for (int j = i + 1; j < list.length; j++) { //那个最小，就记录那个的下标 if (list[min] > list[j]) { min = j; } } //如果选定好的数字不是最大或最小，就需要和选定位置的数字做交换 if (min != i) { n = list[i]; list[i] = list[min]; list[min] = n; } } }

选择排序也没什么难度，不过最大的难度就是在于容易忘记一些细节；
三、插入排序

文章图片
算法描述：
对于没有排好的数据，从有序队列的后面开始比较，逐步前移找到合适的位置
代码样例：

public static void sort(int[] list) { int n; int min; //从1开始，就是选定第一个数为排好序的序列 for (int i = 1; i < list.length; i++) { //从第二个数字开始插入 min = i; //遍历前面的有序数组，直到第一个 for (int j = i - 1; j >= 0; j--) { //如果满足可以交换的条件，就交换 if (list[min] < list[j]) { n = list[min]; list[min] = list[j]; list[j] = n; //然后记录交换后的下标，因为下次还要用 min = j; } } } }

四、希尔排序算法描述：
1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
算法步骤：

先把数组分为多个间隔相同的小数组，小数组长度可以不同，但是间隔要相同
遍历每个小数，并对每个小数组进行插入排序
把间隔缩小然后再次遍历并执行插入排序
直到间隔为1

代码样例：

public static void sort(int[] list) { int step = list.length; while (true) { //每次把间隔缩小2倍 step /= 2; //遍历每一组的第一个 for (int i = 0; i < step; i++) { //遍历每一组的第二个到最后一个 for (int j = i + step; j < list.length; j += step) { //内部进行插入排序，这是一个步长不一定为1的插入排序 int min = j; int n; for (int k = j - step; k >= 0; k -= step) { if (list[min] < list[k]) { n = list[min]; list[min] = list[k]; list[k] = n; min = k; } } } } //当步长，或者间隔为1时，表示最后一次遍历，遍历结束退出循环 if (step == 1) break; } }

五、归并排序

文章图片
算法描述：
归并排序是采用分治的方法，把一组数据分成多段，不断的分段分到足够小，然后把每一小段合并然后排序，一直合并排序到最后；
算法步骤：

根据需求把一组数据分段
从第一段数据开始排序
排好之后和后面的合并排序
重复以上两个步骤只到把每一段数据都添加进去

代码样例：

public static void sort(int[] list, int start, int end) { //划分到只有一个元素时，不需要排序 if (start < end) { //将数组划分成多段 int mid = (start + end) / 2; //将数组划分后左边进行排序 sort(list, start, mid); //将数组划分后的右边进行排序 sort(list, mid + 1, end); //把左右合并到一起 //也就是当左只有一个，右边也只有一个的时候开始排序， //然后最终的递归，返回排好序的左边数组，和右边等量的数组合并 //依据之前划分的大小不断合并 get(list, start, mid, end); } }private static void get(int[] list, int start, int mid, int end) { //由于不一定是等量大小的左右数组，所以借助传入的mid来确定左右数组 //租借临时数组存放排序元素 int[] res = new int[end + 1]; //分别标记左右数组的起始位置 int left = start; int right = mid + 1; //标记存放在临时数组的元素位置 int k = start; //开始排序，不断对比两边的数据，只到某一边的数据全部存入完毕 while (left <= mid && right <= end) { if (list[left] <= list[right]) { res[k++] = list[left++]; } else { res[k++] = list[right++]; } } //把左边或者右边的数组剩下的元素，直接放进去 while (left <= mid) { res[k++] = list[left++]; } while (right <= end) { res[k++] = list[right++]; } //把排好序的数据覆盖原数组 for (int i = start; i <= end; i++) { list[i] = res[i]; } }

下一篇地址在这里： Java实现十大经典排序算法–下