会飞的鱼

奇乐云
首页 » Java » java番外篇之数组4种基本算法(冒泡排序)(选择排序)(选择排序)(二分法查找)

java番外篇之数组4种基本算法(冒泡排序)(选择排序)(选择排序)(二分法查找)

一、冒泡排序:

(1)原理:

1、从第一个数据开始,与第二个数据相比较,如果第二个数据小于第一个数据,则交换两个数据的位置。

2、指针由第一个数据移向第二个数据,第二个数据与第三个数据相比较,如果第三个数据小于第二个数据,则交换两个数据的位置。

3、依此类推,完成第一轮排序。第一轮排序结束后,最大的元素被移到了最右面。

4、依照上面的过程进行第二轮排序,将第二大的排在倒数第二的位置。

5、重复上述过程,没排完一轮,比较次数就减少一次。

(2)例子:

待排序数据:7, 6, 9, 8, 5,1

第一轮排序过程:指针先指向7,7和6比较,6<7,交换6和7的位置,结果为:6,7,9,8,5,1

指针指向第二个元素7,7和9比较,9>7,不用交换位置,结果仍为:6,7,9,8,5,1

指针指向第三个元素9,比较9和8,8<9,交换8和9的位置,结果为:6,7,8,9,5,1

指针指向第四个元素9,比较9和5,5<9,交换5和9,结果为:6,7,8,5,9,1

指针指向第五个元素9,比较9和1,1<9,交换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次。

(3)编码思路:

需要两层循环,第一层循环i表示排序的轮数,第二层循环j表示比较的次数。

(4)代码实现:

(5)冒泡排序算法总结:

N个元素需要排序N-1轮;

第i轮需要比较N-i次;

N个元素排序,需要比较n(n-1)/2次;

冒泡排序的算法复杂度较高,为O(n*n)

二、选择排序

选择排序是对冒泡排序的改进,它的比较次数与冒泡排序相同,但交换次数要小于冒泡排序。当数据量较大时,效率会有很大的提升,但时间复杂度仍为O(n*n)

(1)原理:

1、从第一个元素开始,分别与后面的元素向比较,找到最小的元素与第一个元素交换位置;

2、从第二个元素开始,分别与后面的元素相比较,找到剩余元素中最小的元素,与第二个元素交换;

3、重复上述步骤,直到所有的元素都排成由小到大为止。

(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次。

(3)编码思路:

需要两次循环,第一层循环i表示每轮指针指向的位置,将最小值min初始化为第i个元素,第二层循环从j=i+1开始,分别与min比较,如果小于min,则更新min的值,内层循环结束后;交换min元素和第i个元素的位置。以此类推进行下一轮循环,直到i=length时停止循环。当i=length时,说明小的元素已经全部移到了左面,因此无需进行内层循环了。

(4)编码实现:

(5)选择排序总结:

N个元素需要排序N-1轮;

第i轮需要比较N-i次;

N个元素排序,需要比较n(n-1)/2次;

选择排序的算法复杂度仍为O(n*n);

相比于冒泡排序,选择排序的交换次数大大减少,因此速度要快于冒泡排序

三、插入排序

插入排序是简单排序中最快的排序算法,虽然时间复杂度仍然为O(n*n),但是却比冒泡排序和选择排序快很多。

(1)原理:

1、将指针指向某个元素,假设该元素左侧的元素全部有序,将该元素抽取出来,然后按照从右往左的顺序分别与其左边的元素比较,遇到比其大的元素便将元素右移,直到找到比该元素小的元素或者找到最左面发现其左侧的元素都比它大,停止;

      2、此时会出现一个空位,将该元素放入到空位中,此时该元素左侧的元素都比它小,右侧的元素都比它大;

3、指针向后移动一位,重复上述过程。每操作一轮,左侧有序元素都增加一个,右侧无序元素都减少一个。

(2)例子:
待比较数据:7, 6, 9, 8, 5,1

第一轮:指针指向第二个元素6,假设6左面的元素为有序的,将6抽离出来,形成7,_,9,8,5,1,从7开始,6和7比较,发现7>6。将7右移,形成_,7,9,8,5,1,6插入到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比较,发现8<9,将9向后移,形成6,7,_,9,5,1,8插入到空位中,结果为: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)编码分析:

需要两层循环,第一层循环index表示上述例子中的指针,即遍历从坐标为1开始的每一个元素;第二层循环从leftindex=index-1开始,leftindex--向左遍历,将每一个元素与i处的元素比较,直到j处的元素小于i出的元素或者leftindex<0;遍历从i到j的每一个元素使其右移,最后将index处的元素放到leftindex处的空位处。

(5)插入排序分析:

      时间复杂度,由于仍然需要两层循环,插入排序的时间复杂度仍然为O(n*n)。
比较次数:在第一轮排序中,插入排序最多比较一次;在第二轮排序中插入排序最多比较二次;以此类推,最后一轮排序时,最多比较N-1次,因此插入排序的最多比较次数为1+2+...+N-1=N*(N-1)/2。尽管如此,实际上插入排序很少会真的比较这么多次,因为一旦发现左侧有比目标元素小的元素,比较就停止了,因此,插入排序平均比较次数为N*(N-1)/4。

移动次数:插入排序的移动次数与比较次数几乎一致,但移动的速度要比交换的速度快得多。

综上,插入排序的速度约比冒泡排序快一倍(比较次数少一倍),比选择排序还要快一些,对于基本有序的数据,插入排序的速度会很快,是简单排序中效率最高的排序算法。

[1]排序

//选择排序 ,
function selectionSort(arr){
    for (var i = 0; i < arr.length; i++) {
        for (var j = i+1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                var temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}
alert(selectionSort(arr))

//冒泡排序
function bubbleSort(arr){
    for (var i = 0; i < arr.length-1; i++) {
        for (var j = 0; j < arr.length-1-i; j++) {
        //每次比较都会确定一个最小数,所以j < arr.length-1-i
            if (arr[j] > arr[j+1]) {
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}
alert(bubbleSort(arr))

// 插入排序,往前比较,如果当前数比前一个小则进行第二个循环操作,反之则直接进入下次外层循环
function insertSort(arr){
    for (var i = 1; i < arr.length; i++) {
        var temp = arr[i];
        for (var j = i-1; j >=0 && temp < arr[j]; j--) {
            arr[j+1] = arr[j];
            arr[j] = temp;
        }
    }
    return arr;
}
alert(insertSort(arr))

// 快速排序
function quickSort(arr){
    // 如果数组长度<=1 ,则直接返回
    if (arr.length <= 1) return arr;
    //
    var bisectionIndex = Math.floor(arr.length/2);
    // 找基准,把基准从原数组中删除
    var bisection = arr.splice(bisection,1)[0];
    console.log(bisection);

    // 定义作用数组
    var left = [];
    var right = [];

    // 比基准小的放left ,比基准大的放right
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] <= bisection) {
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }
    //递归
    return quickSort(left).concat([bisection],quickSort(right));
}
alert(quickSort(arr))

[2]二分法查找
常见对象(数组高级二分查找原理图解)
* A:画图演示
* 二分查找  查找元素对应的索引

* 前提:数组元素有序

e9a26386b6153e417c78794b3717b799_70.png

常见对象(数组高级二分查找代码实现及注意事项)
* A:案例演示
* 数组高级二分查找代码
* B:注意事项
* 如果数组无序,就不能使用二分查找。

* 因为如果你排序了,但是你排序的时候已经改变了我最原始的元素索引。

public class Demo2_Array2 {
	public static void main(String[] args) {
		int[] arr = {11,22,33,44,55};
		System.out.println(fac(arr, 22));
		
	}
	private static int fac(int[] arr, int valte) {
		int min = 0;
		int max =arr.length -1;
		int mid =(min + max) /2;
		while( arr[mid] != valte) {		//当中间值不等于要找的值,开始循环
			if (arr[mid] > valte) {		//当中间值小于要找的值
				max = mid -1;			//最小索引改变
			}else if(arr[mid] < valte) {//当中间值大于要找的值
				min = mid+1;			//最大索引改变
			}
			mid =(min + max) /2;		//无论最大索引还是最小索引改变 中间索引都会随之改变
			if(min > max) {			
				return -1;				//如果最小索引大于了最大索引
			}
		}
		return mid;
	}	
}


文章如无特别注明均为原创! 作者: admin, 转载或复制请以 超链接形式 并注明出处 奇乐云-建站源码,网络技术,免空免域,模板主题,电脑软件,超级博客
原文地址《 java番外篇之数组4种基本算法(冒泡排序)(选择排序)(选择排序)(二分法查找)》发布于2019-1-27

分享到:
打赏

评论

游客

切换注册

登录

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录
切换登录

注册