程序地带

经典排序算法:冒泡、选择、插入、希尔、归并


经典排序算法

排序算法分类 算法的性质: 稳定:如果a原本在b前面,且a == b,排序后a仍然在b前面 不稳定:如果a原本在b前面,且a == b,排序后a可能在b后面 内排序:所有排序操作都在内存中进行 外排序:由于数据太大,因此把数据放在磁盘中,排序通过磁盘和内存的数据传输才能进行


一、 冒泡排序(Bubble Sort)
public void BubbleSort(int[] arr){
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
//相邻两个元素作比较,如果前面元素大于后面,进行交换
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
}

我的理解: 冒泡排序的核心,是 “泡”。也就是它会尝试把每一个值都当作大的气泡,要将他冒到数组尾部。 可以想象最差的情况,一个严格单调递减的数组,比如 9 8 7 6 5 4 3 2 1 0 ,先冒9,9跟8比较,交换,9跟7比较,交换。。。一直到9跟0比较,交换、结束9的冒泡。 此刻数组为 8 7 6 5 4 3 2 1 0 9。再冒8,8跟7比较,交换,跟6比较,交换。。。跟0比较,交换,注意,最后一位是9,不用比较了,因为9已经和8比较过了,这也就是为什么内层循环里,j < array.length – 1 -i的原因。 可以看到,这里的实现比较相邻两个值用的是小于,因此是稳定的,它不会把相等的值也交换位置。


二、 选择排序(Selection Sort)
public static int[] selectionSort(int[] array) {
if (array.length == 0)
return array;
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i; j < array.length; j++) {
if (array[j] < array[minIndex]) //找到最小的数
minIndex = j; //将最小数的索引保存
}
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
return array;
}

我的理解: 选择排序的原理很简单,把数组看成左右两部分,即有序区、无序区,每次都从无序区选择最小的一个值,将它加入到有序区右边,也就是无序区最左侧的值和无序区的最小值交换。有序区和无序区的分解线为i,即 [0 , i)和[I , length – 1]。


三、 插入排序(Insertion Sort)
public static int[] insertionSort(int[] array) {
if (array.length == 0)
return array;
int current;
for (int i = 0; i < array.length - 1; i++) {
current = array[i + 1];
int preIndex = i;
//注意,为了插入,需要把比current大的值后移。不用担心current的值,他已经被保留了
while (preIndex >= 0 && current < array[preIndex]) {
array[preIndex + 1] = array[preIndex];
preIndex--;
}
//将current的值放在preIndex后面,也就是放在那个比current小的值后面
array[preIndex + 1] = current;
}
return array;
}

我的理解: 插入排序其实和选择排序很像,即将整个数组分为两个部分,有序区、无序区。将无序区第一个元素i+1插入到有序区内,其插入方式是倒序遍历有序区。倒序终止的条件是下标越界或者已经找到合适位置(元素 i + 1大于等于,这个等于值得注意,它前面的值) 。当有序区的长度为length – 1,而无序区仅仅一个元素时,可以看出,最后一个无序元素会倒着冒泡到合适的位置去。


以上三种排序算法,时间复杂度都是n^2 ,他们每一次比较都需要遍历无序的元素,每次把无序的元素数量减一,效率较低


四、 希尔排序
public static int[] ShellSort(int[] array) {
int len = array.length;
int temp, gap = len / 2;
while (gap > 0) {
for (int i = gap; i < len; i++) {
temp = array[i];
int preIndex = i - gap;
while (preIndex >= 0 && array[preIndex] > temp) {
array[preIndex + gap] = array[preIndex];
preIndex -= gap;
}
array[preIndex + gap] = temp;
}
gap /= 2;
}
return array;
}

我的理解: 希尔排序重要的是这个gap。 其实希尔排序是一个不断两两比较的排序,这句话是废话,都是两两比较的。 每一次for循环中,使用一个特定的gap来确定每次比较哪两个值(preIndex和i),如果preIndex的值较大,则将i的值赋为preIndex。 注意,while循环内使用的下标并不是preIndex和i,而是preIndex和preIndex + i,在最后一句将下标都向前移动了一个preIndex,这样的就可以在下一次while循环处理同样间隔此gap大小的两个值。 每次for循环中,都预先用temp保存了第一次、最右端的i的值,而每次while循环都保留了preIndex的值,因此,每个for循环的最后会把temp的值赋给i,当然这个preIndex + gap。 每次for循环都会使gap的值减半,在最后gap一定会等于1,因为3/2 或者 2/2都是等于1的,当gap等于1的时候,其实就是一个插入排序。 希尔排序的时间复杂度和前面的冒泡排序、选择排序、插入排序不一样,并不是n的平方。但是具体如何计算我也不明白,只是感觉先进行了较大gap的交换后,节省了逐个冒泡那样逐个比较的时间。冒泡排序、选择排序、插入排序,这三种我们都可以看到对元素逐个比较的操作,而且他们每次的比较,收益都是使下一次的比较次数少1,而希尔排序的神奇之处在于,随着gap的减小,其收益越来越大,交换的次数减少的的幅度应该也是越来越大的。


五、 归并排序(Merge Sort)

经典的递归写法:


public static int[] mergeSort(int[] arr, int left, int right) {
// 如果 left == right,表示数组只有一个元素,则不用递归排序
if (left < right) {
// 把大的数组分隔成两个数组
int mid = (left + right) / 2;
// 对左半部分进行排序
arr = mergeSort(arr, left, mid);
// 对右半部分进行排序
arr = mergeSort(arr, mid + 1, right);
//进行合并
merge(arr, left, mid, right);
}
return arr;
}
//其实merge的过程也是比较的过程
// 合并函数,把两个有序的数组合并起来
// arr[left..mid]表示一个数组,arr[mid+1 .. right]表示一个数组
private static void merge(int[] arr, int left, int mid, int right) {
//先用一个临时数组把他们合并汇总起来
int[] a = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
a[k++] = arr[i++];
} else {
a[k++] = arr[j++];
}
}
while(i <= mid) a[k++] = arr[i++];
while(j <= right) a[k++] = arr[j++];
// 把临时数组复制到原数组
for (i = 0; i < k; i++) {
arr[left++] = a[i];
}
}

我的理解: 归并排序最重要的使使用了递归,当然也有非递归的写法,但是其思想是递归。 递归的话注意要有终止条件,


未完待续,先发表出来看看效果。后面还会记录我的leetcode的简单题之旅,我会先按标签刷完所有leetcode的简单题目


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_40545731/article/details/112760938

随机推荐

神奇的图片处理技术,隐藏信息,点击才见

这是一种神奇的图片处理方式,可以让我们隐藏一部分图片的内容。当用户点击查看图片的时候,会有不同的内容显示出来!先看一下图片的效果(在CSDN下&...

圣手书生肖让 阅读(688)

学习C语言的笔记

《C和指针》笔记持续更新,如果有错误的话,欢迎评论和私信一、用到指针时一定要思考的一些问题它指向谁!能不能访问!是否会导致内存泄漏!二、一些零散...

Troke 阅读(961)

博客搬家!

最新的博客地址:http://blog.zhangkexuan.cn大致内容围绕游戏开发展开,感兴趣的可以看看,欢迎大佬互加友链。...

zkx_jhun 阅读(151)

登录功能的设计点

功能、性能、界面、安全、易用、网络1、账号输入框低层是否有灰色字体的信息提示2、密码输入框低层是否有灰色字体的信息提示3、账号不符合格式要求时,是否有错误提示4、账号为空时,...

似曾相识。 阅读(847)

WPF学习日记37

1.ASCII码解析:[1]0~31及127是控制字符或通信专用字符;[2]32~126是字符,其中48~57为0~9十个阿拉伯数字,65~90...

shengshengwang 阅读(973)

gazebo修改背景图片

gazebo自定义地面背景图片很多时候,我们的gazebo中需要使用带有丰富纹理的模型,比如,双目计算视差等等(题外话,很多人都说...

zhuhanzhi 阅读(570)