面试常用排序算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了面试常用排序算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2283字，纯文字阅读大概需要4分钟。

内容图文

冒泡排序

基本思路：

两两比较相邻记录的数，如果反序则交换，直到没有反序的记录为止。

代码实现要点：

• 两个for循环，外层循环控制排序的趟数，内层循环控制比较的次数

• 每趟过后，比较的次数都应该要减1

优化：如果一趟排序后也没有交换位置，那么该数组已有序～

public void bubble_sort(int srr[]) {
		
		boolean flag = true;
		for (int i = 0; i < srr.length && flag; i++) {
			
			flag = false;	//一轮下来没有交换，说明已经排好，退出循环
			for(int j = srr.length-1; j >i; j--) {
			    if(srr[j] < srr[j-1]) {
                  	      int temp = srr[j];	//交换
                              srr[j] = srr[j-1];
                              srr[j-1] = temp;
                  
			      flag = true;
			    }
			}
		}	
	}

选择排序

基本思路：

• 找到数组中最小的元素，与数组第一位元素交换
• 当只有一个数时，则不需要选择了，因此需要n-1趟排序，比如10个数，需要9趟排序

思路和冒泡排序差不多，先选择最小（或最大）值，再放入指定的位置

public void select_sort(int arr[]) {
		
		int min;
		for (int i = 0; i < arr.length-1; i++) {
		    min = i;
		    for (int j = i+1; j < arr.length; j++) {
			if(arr[min] > arr[j]) {	//每次和标记的最小值相比
			    min = j;
			}
		    }
		    if(min != i) {
                       int temp = arr[min];	//交换
                       arr[min] = arr[i];
                       arr[i] = temp;
		    }
		}
		
	}

插入排序

思路：

• 将一个元素插入到已有序的数组中，在初始时未知是否存在有序的数据，因此将元素第一个元素看成是有序的
• 与有序的数组进行比较，比它大则直接放入，比它小则移动数组元素的位置，找到个合适的位置插入
• 当只有一个数时，则不需要插入了，因此需要n-1趟排序，比如10个数，需要9趟排序

public void insertSort(int ins[]) {

		int i,j,temp;
		for (i = 1; i < ins.length; i++) {
			temp = ins[i]; // 保存每次需要插入的那个数
			
			for (j = i; j > 0 && ins[j - 1] > temp; j--) { // 优化：若比有序数组最大值还大，则不动
				ins[j] = ins[j - 1]; // 把大于需要插入的数往后移动。最后不大于temp的数就空出来j
			}
			ins[j] = temp; // 将需要插入的数放入这个位置
		}

	}

快速排序

基本思路

• 在数组中找一个元素(节点)，比它小的放在节点的左边，比它大的放在节点右边。一趟下来，比节点小的在左边，比节点大的在右边。
• 不断执行这个操作....

public static void quickSort1(int[] items,int L, int R){

        int i = L;
        int j = R;

        //支点
        int chosenItem = items[(L+R)/2];

        while (i <= j){

            //从左边开始寻找直到比支点大的数
            while (chosenItem > items[i]){
                i++;
            }
            //从右边开始寻找直到比支点小的数
            while (chosenItem < items[j]){
                j--;
            }

            if (i <= j){
                //交换
                int temp = items[i];
                items[i] = items[j];
                items[j] = temp;

                i++;
                j--;
            }
        }

        //“左边”再做排序，直到左边剩下一个数(递归出口)
        if (L < j){
            quickSort1(items,L,j);
        }
        //“右边”再做排序，直到右边剩下一个数(递归出口)
        if (i < R){
            quickSort1(items,i,R);
        }
    }

内容总结

以上是互联网集市为您收集整理的面试常用排序算法全部内容，希望文章能够帮你解决面试常用排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---