|
大纲：很早之前就知道冒泡、选择、插入，二分查找法却没有详细的研究过他们之间的区别，今天就静下来，将它们好好总结一下，按照自己的理解和想法，将它们的原理写出来，加深下自己的印象。 1：冒泡排序：原理：冒泡顾名思义，就像气泡从水底冒出一样，它的排序方式是：研究了一下，它给人的感觉是像近视眼一样，它只能看见自己和紧挨着自己的下一个数字，所以它的排序方式也就是将比较元素和紧挨着自己的元素比较看是否交换位置，然后持续这个过程，比较的一直都是紧挨着的两个元素。下面看代码吧，再代码里面再详细解释。- package wjwei;
- public class bubbleSort {
- /**
- * @param args
- */
- //定义排序的数组
- static float arr[]={3.5f,4.5f,4,2,7,1};
- //定义temp用于交换时充当中间元素
- static float temp=0;
- public static void main(String[] args) {
- //外层循环，拿着数组中的元素和其它元素逐个比较
- for(int i=0;i<arr.length-1;i++){
- /*内层循环，就是将0元素的值拿着和1元素的比较，0元素值大于1元素就交换0和1的值，不大于就开始循环j++比较1元素值和2元素的值，循环，直到达到了arr.length(),结束内层循环，此时就将数组中最大的数放在了最高位置。然后开始外层循环i++,开始第二圈的内层循环，比较出除了最大值之外的最大值，这句话的原因是因为第一圈时候已经把最大值得到放在它的正确位置，所以以后也不用再比较它了，这就是i<arr.length-1;的原因。如此外循环结束，则得到了有序的数组*/
- for(int j=0;j<arr.length-1-i;j++){
- if(arr[j]>arr[j+1]){
- //换位
- temp=arr[j];
- arr[j]=arr[j+1];
- arr[j+1]=temp;
- }
-
- }
-
- }
- for(int k=0;k<arr.length;k++){
- System.out.print(arr[k]+"\t");
- }
- }
- }
总结：冒泡排序就是将未排序的元素之间逐个比较并逐个的交换位置。详细介绍和总结完冒泡排序，下面就是选择排序了，
详细介绍和总结完冒泡排序，下面就是选择排序了
2、选择排序：选择排序是冒泡排序的升级。它和冒泡相比，交换的次数减少了，但是比较的次数还是一样的。 原理：选择实际就是选出数组中未排序的最大或者最小值，然后将其放在自己的位置。下面看代码：- package wjwei;
- public class selectSort {
- public static void main(String []args){
- int brr[]={4,9,39,13,43,5};
- Select select=new Select();
- select.sort(brr);
- }
- }
- class Select{
- public void sort(int arr[]){
- //定义交换变量
- int temp=0;
- //外层循环，比较并交换位置
- for(int i=0;i<arr.length-1;i++){
- //定义min用于接收数组中的最小值
- int min=arr[i];
- //定义minid接收最小值的小标
- int minid=i;
- //内层循环，找出为比较数组中的最小的下标
- for(int j=i+1;j<arr.length;j++){
- if(arr[i]>arr[j]){
- min=arr[j];
- minid=j;
- }
- }
- /*交换最小值的位置备注：从这里可以看出和冒泡的区别，冒泡是在内层循环的时候进行位置的交换，而选择排序，则是先选出最小值，在外层循环进行位置交换，这样就可与节省下了内层循环时的交换次数。*/
- temp=arr[i];
- arr[i]=arr[minid];
- arr[minid]=temp;
- }
- for(int k=0;k<arr.length;k++){
- System.out.print(arr[k]+"\t");
- }
- }
- }
- 总结：选择排序相比冒泡效率高了，减少了交换位置的次数。
- 3、插入排序：是将所插入的元素，插入已经有一定顺序的数组中。
- 插入原理：1、首先要定义一个标记的元素，好进行判断要往哪里插入；2、要和标记元素进行比较，看插在标记元素的哪边。3、如果是右边就直接插入，如果是左边则需要和标记位的左边的每一位进行比较，找寻插入的位置。
- 下面看代码以及详细解释：
- package wjwei;
- public class charu {
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- int arr[]={3,1,-4,9,-8,5,-3,7,0,3,5,56,45};
- Insert insert=new Insert();
- insert.sort(arr);
- }
- }
- class Insert{
- public void sort(int arr[]){
- //for循环，从下标1开始遍历数组，进行插入
- for(int i=1;i<arr.length;i++){
- //定义插入的数据元素
- int charu=arr[i];
- //定义标记位置，也就是插入的位置
- int yuan=i-1;
- /*判断，如果标记位置大于等于0并且插入的数据元素小于标记的元素则进入循环将标记数据往右移，然后对标记位置进行--操作，使要插入的数据与标记左侧各个数据相比，满足循环的条件就进行右移操作，不满足循环的条件就跳出循环得到自己的位置。*/
- while(yuan>=0&&charu<arr[yuan]){
- //把前面存在的那个数的数向后移动一位
- arr[yuan+1]=arr[yuan];
- //让yuan向前一位
- yuan--;
- }
- //不满足比标记元素小，也不满足标记位置大于0就将插入的元素放在标记位置的右边
- arr[yuan+1]=charu;
- }
- //输出最后结果
- for(int i=0;i<arr.length;i++){
- System.out.print(arr[i]+"\t");
- }
- }
-
- }
总结：插入排序，前期比较次数较少，相比较冒泡每次都要比较每次都要交换，和选择排序的每次都要比较全部的元素相比，它速度要快。
小结：前面都是简单排序的方式。 4,、二分查找：二分查找是很常见而且高效的查找方式，比普通查找速度快的多。普通查找：遍历数组和查询值进行比较； 二分查找：定义中间值和所查找值进行比较，小于中间值就查找中间值左边的值，大于则相反。所以，二分查找要满足被 查的数组是有序排列的。下面代码分别是普通查找，二分查找和递归实现的二分查找。- package boke2;
- import java.util.Arrays;
- public class Dichotomy {
- /**
- * 普通查找和二分查找法
- */
- public static void main(String[] args) {
- int[] num = { 15, 34, 36, 45, 52, 63 };
- Arrays.sort(num);
- int n = 45;
- // int j = findNum(num,n);
- // int j = DichotomybyCommon(num, n);
- int j = Dichotomybydigui(num, 0, num.length, n);
- System.out.println(j);
- }
- // 普通查找法
- public static int findNum(int[] num, int n) {
- for (int i = 0; i < num.length; i++) {
- if (num[i] == n)
- return i;
- }
- return 0;
- }
- // 普通二分查找
- @SuppressWarnings("unused")
- private static int DichotomybyCommon(int[] num, int n) {
- int left, right, among;
- left = 0;
- right = num.length - 1;
- while (left <= right) {
- among = (left + right) / 2;
- if (num[among] == n)
- return among;
- else if (n < num[among])
- right = among - 1;
- else
- left = among + 1;
- }
- return -1;
- }
- // 递归二分查找
- private static int Dichotomybydigui(int[] num, int left, int right,
- int keyNum) {
- int among = (left + right) / 2;
- if (left <= right) {
- if (num[among] == keyNum)
- return among;
- else if (keyNum < num[among])
- //使用递归算法自身调用自身
- return Dichotomybydigui(num, left, among - 1, keyNum);
- else
- return Dichotomybydigui(num, among + 1, right, keyNum);
- }
- return -1;
- }
- }
|
收藏
淘帖
踩
