企业网站开发开题报告,好商网的网站可以做中英文切换吗,外行怎么做网站,常用的行业管理系统简单排序算法#xff1a;冒泡排序#xff0c;选择排序#xff0c;插入排序
一、冒泡排序
1.1 原理#xff1a;
从第一个数据开始#xff0c;与第二个数据相比较#xff0c;如果第二个数据小于第一个数据#xff0c;则交换两个数据的位置指针由第一个数据移向第二个数…简单排序算法冒泡排序选择排序插入排序
一、冒泡排序
1.1 原理
从第一个数据开始与第二个数据相比较如果第二个数据小于第一个数据则交换两个数据的位置指针由第一个数据移向第二个数据第二个数据与第三个数据相比较如果第三个数据小于第二个数据则交换两个数据的位置依此类推完成第一轮排序。第一轮排序结束后最大的元素被移到了最右面依照上面的过程进行第二轮排序将第二大的排在倒数第二的位置重复上述过程没排完一轮比较次数就减少一次
1.2 例子
待排序数据7, 6, 9, 8, 5,1
第一轮排序过程
指针先指向77和6比较67交换6和7的位置结果为6,7,9,8,5,1
指针指向第二个元素77和9比较97不用交换位置结果仍为6,7,9,8,5,1
指针指向第三个元素9比较9和889交换8和9的位置结果为6,7,8,9,5,1
指针指向第四个元素9比较9和559交换5和9结果为6,7,8,5,9,1
指针指向第五个元素9比较9和119交换1和9的位置结果为6,7,8,5,1,9
第一轮排序结束后最大的数字9被移到了最右边。
进行第二轮排序过程同上只是由于最大的9已经放在最右边了因此不用在比较9了少了一次比较 第二轮结束的结果为6,7,5,1,8,9
第三轮结果6,5,1,7,8,9
第四轮比较结果5,1,6,7,8,9
第五轮比较结果1,5,6,7,8,9
最终排序结果为1,5,6,7,8,9由上可知N个数据排序需要进行N-1轮排序第i轮排序需要的比较次数为N-i次。
1.3 代码实现
//1.冒泡排序(默认升序)O(n*n)
public void bobSort(int [] arr) {if(arr null || arr.length2) {return;}int temp0, len arr.length;for(int i0;ilen;i) {for(int ji1;jlen;j) {if(arr[i] arr[j]) {temp arr[i];arr[i] arr[j];arr[j] temp;}}}
}二、选择排序
选择排序是对冒泡排序的改进它的比较次数与冒泡排序相同但交换次数要小于冒泡排序。当数据量较大时效率会有很大的提升但时间复杂度仍为O(n*n)
2.1 原理
从第一个元素开始分别与后面的元素向比较找到最小的元素与第一个元素交换位置从第二个元素开始分别与后面的元素相比较找到剩余元素中最小的元素与第二个元素交换重复上述步骤直到所有的元素都排成由小到大为止
2.2 例子
待比较数据7, 6, 9, 8, 5,1
第一轮此时指针指向第一个元素7找出所有数据中最小的元素即1交换7和1的位置排序后的数据为1,6,9,8,5,7
第二轮第一个元素已经为最小的元素此时指针指向第二个元素6找到6,9,8,5,7中最小的元素即5交换5和6的位置排序后的结果为1,5,9,8,6,7
第三轮前两个元素为排好序的元素此时指针指向第三个元素9找到9,8,6,7中最小的元素即6交换6和9的位置排序后的结果为1,5,6,8,9,7
第四轮前三个元素为排好序的元素此时指针指向第四个元素8找到8,9,7中最小的元素即7交换8和7的位置排序后的结果为1,5,6,7,9,8
第五轮前四个元素为排好序的元素此时指针指向第五个元素9找到9,8中最小的元素即8交换9和8的位置排序后的结果为1,5,6,7,8,9
到此全部排序完成。
分析从上面的原理可以看出与冒泡排序不同选择排序每排完一轮都把最小的元素移到了最左面然后下一轮排序的比较次数比上一轮减少一次即第i轮排序需要比较N-i次。因此和冒泡排序一样N个数据比较大小需要排序N-1轮第i轮排序需要比较N-i次。
2.3 代码实现
//2.选择排序,相对冒泡来说改进在于交换的次数减少
//(O(n*n))
public void chooseSort(int [] arr) {if(arr null || arr.length2) {return;}int len arr.length, curIndex 0, temp0 ;for(int i0;ilen;i) {curIndex i;for(int j0;jlen-i;j) {if(arr[curIndex] arr[j]) {curIndex j;}}temp arr[curIndex];arr[curIndex] arr[len-i-1];arr[len-i-1] temp;}
}3、插入排序
插入排序是简单排序中最快的排序算法虽然时间复杂度仍然为O(n*n)但是却比冒泡排序和选择排序快很多。
3.1 原理
将指针指向某个元素假设该元素左侧的元素全部有序将该元素抽取出来然后按照从右往左的顺序分别与其左边的元素比较遇到比其大的元素便将元素右移直到找到比该元素小的元素或者找到最左面发现其左侧的元素都比它大停止此时会出现一个空位将该元素放入到空位中此时该元素左侧的元素都比它小右侧的元素都比它大指针向后移动一位重复上述过程。每操作一轮左侧有序元素都增加一个右侧无序元素都减少一个
3.2 例子
待比较数据7, 6, 9, 8, 5,1
第一轮指针指向第二个元素6假设6左面的元素为有序的将6抽离出来形成7,,9,8,5,1从7开始6和7比较发现76。将7右移形成,7,9,8,5,16插入到7前面的空位结果6,7,9,8,5,1
第二轮指针指向第三个元素9此时其左面的元素6,7为有序的将9抽离出来形成6,7,_,8,5,1从7开始依次与9比较发现9左侧的元素都比9小于是无需移动把9放到空位中结果仍为6,7,9,8,5,1
第三轮指针指向第四个元素8此时其左面的元素6,7,9为有序的将8抽离出来形成6,7,9,,5,1从9开始依次与8比较发现89将9向后移形成6,7,,9,5,18插入到空位中结果为6,7,8,9,5,1
第四轮指针指向第五个元素5此时其左面的元素6,7,8,9为有序的将5抽离出来形成6,7,8,9,,1从9开始依次与5比较发现5比其左侧所有元素都小5左侧元素全部向右移动形成,6,7,8,9,1将5放入空位结果5,6,7,8,9,1。
第五轮同上1被移到最左面最后结果1,5,6,7,8,9。
3.3 代码实现
//插入排序(O(n*n),简单排序算法里效率相对最好的)
public void insertSort(int [] arr) {if(arr null || arr.length2) {return;}int len arr.length, temp0 ;for(int i1;ilen;i) {temp arr[i];int ji-1;for(;j0 arr[j]temp;j--) {arr[j1] arr[j];}if(j ! i-1) {arr[j] temp;}}}4、测试代码
public static void main(String[] args) {Test test new Test();int[] arr {77,29,28,36,33,25,10};test.bobSort(arr);System.out.println(Arrays.toString(arr));test.chooseSort(arr);System.out.println(Arrays.toString(arr));test.insertSort(arr);System.out.println(Arrays.toString(arr));
}5、拓展
侏儒排序类似直接插入排序直接插入排序更优 https://www.cnblogs.com/9-de/p/6600640.html
图书馆排序 基于插入排序做的优化为在每本书之间预留一定的空隙然后在插入的时候就能少移动一些书。说白了就是在插入排序的基础上,给书与书之间留一定的空隙,这个空隙越大,需要移动的书就越少,这是它的思路,用空间换时间
https://blog.csdn.net/u014723529/article/details/41958545
