排序算法之交换(冒泡与快排)

2019/7/24 9:39:56 人评论 次浏览 分类:学习教程

排序算法根据是否需要访问外存,分为内部排序和外部排序。

  • 内部排序是指待排序列完全存放在内存中所进行的排序过程,适合不太大的元素序列。
  • 外部排序是指大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,来达到排序整个文件的目的。

一.内部排序

使用内存,分为插入(直接插入排序  希尔排序)、选择(简单选择排序  堆排序)、交换(冒泡排序  快速排序)、归并、基数。

5.冒泡排序

效率很低,实现简单

  • 基本思想:对相邻的元素进行两两比较,顺序相反则进行交换。每一趟排序都会将最小或最大的元素放置待排数组的末尾,最终达到完全有序。

待排序列:3、1、4、2
第一趟排序结果:1、3、2、4
第二趟排序结果:1、2、3、4
第三趟排序结果:1、2、3、4

最终排序结果为:1、2、3、4

  • 代码实现(Java) 
public class BubbleSort {
	public static void bubbleSort(int[] arr){
        for (int i=0;i<arr.length-1; i++){
            //设定一个标记,作为没有发生数据交换的标志。若此次循环没有进行交换,表示排序完成                
            boolean flag = true;
            //已经有i个元素排好序
            for (int j=1;j<arr.length-i; j++){
                if(arr[j-1] > arr[j]){
                    swap(arr,j-1,j);
                    flag = false;
                }
            }
            System.out.println("第"+(i+1)+"趟排序结果:");
            display(arr);
            if(flag){
                break;
            }
        }
    }
	public static void swap(int[] arr, int a,int b) {
		if(arr[a]>arr[b]) {
			arr[a]=arr[a]+arr[b];
			arr[b]=arr[a]-arr[b];
			arr[a]=arr[a]-arr[b];
		}
	}
	public static void display(int[] arr) {
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+"  ");
		}
		System.out.println();
	}
	public static void main(String[] args) {
		int arr[]= {9,3,1,4,2,7,8,6,5};
		bubbleSort(arr);
		System.out.println("最终排序结果为:");
		display(arr);
	}
}
  • 算法分析

冒泡排序的时间复杂度为O(n^2)。最坏情况,逆序O(n*(n-1)/2);最好情况,顺序O(n-1)。

6.快速排序

基于分治算法

  • 基本思想:
    选择一个基准元素,通常选择第一个元素或最后一个元素。
    通过一趟排序将待排元素分为两部分,一部分元素小于基准元素,另一部分元素大于基准元素。
    此时,基准元素在处于最终序列的正确位置。分别对这两部分使用同样的方法进行排序,直至整个序列有序。
  • 代码实现(Java):
public class QuickSort {
	public static void quickSort(int[] arr) {
		if(arr.length<0 || arr==null) {
			return;
		}
	    quickSort(arr,0,arr.length-1);
	}
	public static void quickSort(int[] arr, int low, int high) {
		if(low>=high) {
			return;
		}else {
			int flag=arr[low];
			int partition=partition(arr,low,high,flag);
			display(arr);
			quickSort(arr,low,partition-1);
			quickSort(arr,partition+1,high);
		}
	}
	public static int partition(int[] arr,int low,int high,int flag) {
		while(low<high) {
			while(low<high && arr[high]>=flag) {
				high--;
			}
			swap(arr,low,high);
			while(low<high && arr[low]<=flag) {
				low++;
			}
			swap(arr,low,high);
		}
		arr[low]=flag;
		return low;
	}
	public static void swap(int[] arr, int a,int b) {
			arr[a]=arr[a]+arr[b];
			arr[b]=arr[a]-arr[b];
			arr[a]=arr[a]-arr[b];
	}
	public static void display(int[] arr) {
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+"  ");
		}
		System.out.println();
	}
	public static void main(String[] args) {
		int[] arr= {57,68,59,52,72,28,96,33,24,19};
		quickSort(arr);
		System.out.println("最终结果:");
		display(arr);
	}
}
  • 算法分析

时间复杂度为O(n*logn),当数据有小到大或由大到小排列时,快速排序的效率最低,时间复杂度为O(n^2)

选择第一个元素作为基准相对简单,但当其为最大或最小值时,快速排序的效率会降低。这时,采用“三项取中法”来避免最值情况出现。

非递归实现

相关资讯

  • 那些我们不愿意承认的事

    很久没有见的老朋友,准确的说应该是很久没有见过的老师,一个比我大两岁的老师,我上初中的时候他从高中回来教我了一年。后来又回去上高中,我上高中的时候他上大学,现在我刚大学毕业他创办了公司。昨日一见依然如故,他还是热爱销售,而我却成了纯粹的技术人员。 看到他…

    2015/6/22 13:12:47

学习教程

共有访客发表了评论 网友评论

验证码: 看不清楚?

    立即查看