图解排序算法

最近觉得自己的编程毫无进展，想修炼下自己的内功，于是就开始复习学习数据结构与算法。其实，编程的人大概都知道一句话“程序等于算法+数据结构”，理解并选用合适的数据结构，还有算法，是编写出优秀程序的前提。在JAVA JDK中，也可以窥探出数据结构算法的重要性，比如HashMap中就用到了数组+链表提高查找、插入效率。个人也想通过总结编写文章的方式提高学习效率，于是有这篇文章。为了逼自己一把，决定以后每周写一篇博客（不一定都是数据结构与算法）。由于鄙人水平有限，加之文采极差，还很少写博客，希望看到文章的各位大佬能提提看法、建议。

一、冒泡排序

1、说明

冒泡排序，每次冒泡都比较相邻两个数的大小，大小关系不对，则交换。如下图，第一躺冒泡下来，最大的值都会被排到正确的位置，也有可能有其他数字处于正确位置。所以一趟下来至少有一个最大的处于正确位置（如下图的9）。

第二趟下来，第一趟后剩下的数字中，最大的8又会处于正确位置（如下图）。

这样最多冒泡n-1次，就会是一个有序的序列

2、 JAVA 代码实现如下

//时间复杂度为O(n^2) 最好时间复杂度O(n) 平均时间复杂度O(n^2)
public static void sort(int numArray[]) {
	if (numArray == null || numArray.length == 0) {
	   return;
	}
	int arrayLength = numArray.length;
	int tmp;
        //这一趟是否有发生交换，如果没有发生交换，说明数组已经是有序的，不需要再冒泡了。
	boolean flag = false;
	//外层：需要length-1次循环比较，需要做n-1次冒泡
	for(int i= 0; i < arrayLength - 1; i++) {
                flag = false;
    		for(int j=0; j < arrayLength -i-1; j++) {
			//内层：每次循环需要两两比较的次数，每次比较后，都会将当前最大的数放到最后位置
			if(numArray[j] > numArray[j+1]) {
				tmp = numArray[j];
				numArray[j] = numArray[j+1];
				numArray[j+1] = tmp;
				flag = true;
			}
		}
		if(!flag) //没有任何交换，数组已经处于有序
			break;
	}
}
复制代码

二、选择排序

1、说明

选择排序如下图，每次都找出剩余中最小的值，将该最小值放到正确位置

2、JAVA代码实现如下

public static void selectSort(int numArray[]) {
	int length = numArray.length;
	int min,pos;
        //每一次循环都会找出剩下中的最小数，放到正确的位置
	for(int i= 0; i < length-1; i++) {
		min = numArray[i];
		pos = i;
                //找出剩余中的最小数
		for(int j = i+1; j < length; j++) {
			if(numArray[j] < min) {
				min = numArray[j];
				pos = j;
			}
		}
		if(pos != i) {
			numArray[pos] = numArray[i];
			numArray[i] = min;
		}
	}
}复制代码

三、插入排序

1、说明

插入排序同我们打扑克牌时排序牌一样，每次抽上一张牌，插入到手上已经有序的牌中。如下例子，我们从第二个数开始，插入到前面中。如下图，第二次，6需要插入到前面5，8之间，所以将8后移，之后将6插入。

2、JAVA代码实现如下

public static void insertSort(int intList[]) {
	int j = 1;
	int i;
	for(; j < intList.length; j++) {
		i = j-1;
		int key = intList[j];
		while(i > -1 && intList[i] > key) {
			intList[i+1] = intList[i];
			i--;
		}
		intList[i+1] = key;
	}
	//时间复制度为O(n^2) ,最好情况时间复杂度O(n),平均时间复杂度O(n^2)
}复制代码

四、快速排序

1、说明

快速排序采用分治的思想，总的思想就是选取一个数字为基准值，并将所有比它小的元素放到它前面，比它大的元素放到它后面，之后基准值就处于正确位置，分别对基准值前后两个数组进行排序，最后就会是有序的。快速排序有多种实现方式，以下是通过左右指针实现。

2、 JAVA代码实现如下

public static void quickSort(int numArray[],int _left, int _right) {
	int left = _left;
    int right = _right;
    int temp = 0;
    if(left <= right){   //待排序的元素至少有两个的情况
        temp = numArray[left];  //待排序的第一个元素作为基准元素
        while(left != right){   //从左右两边交替扫描，直到left = right

            while(right > left && numArray[right] >= temp)  
                 right --;        //从右往左扫描，找到第一个比基准元素小的元素
            numArray[left] = numArray[right];  //找到这种元素arr[right]后与arr[left]交换

            while(left < right && numArray[left] <= temp)
                 left ++;         //从左往右扫描，找到第一个比基准元素大的元素
            numArray[right] = numArray[left];  //找到这种元素arr[left]后，与arr[right]交换

        }
        numArray[right] = temp;    //基准元素归位
        quickSort(numArray,_left,left-1);  //对基准元素左边的元素进行递归排序
        quickSort(numArray, right+1,_right);  //对基准元素右边的进行递归排序
    }     
}复制代码

五、归并排序

1、说明

归并排序也是分治思想，先将所有元素分离开，并进行逐步排序，原理如下图

2、 JAVA代码实现如下

public static int[] sort(int [] a) {
    if (a.length <= 1) {
        return a;
    }
    int num = a.length >> 1;
    int[] left = Arrays.copyOfRange(a, 0, num);
    int[] right = Arrays.copyOfRange(a, num, a.length);
    return mergeTwoArray(sort(left), sort(right));
}

public static int[] mergeTwoArray(int[] a, int[] b) {
    int i = 0, j = 0, k = 0;
    int[] result = new int[a.length + b.length]; // 申请额外空间保存归并之后数据

    while (i < a.length && j < b.length) { //选取两个序列中的较小值放入新数组
        if (a[i] <= b[j]) {
            result[k++] = a[i++];
        } else {
            result[k++] = b[j++];
        }
    }

    while (i < a.length) { //序列a中多余的元素移入新数组
        result[k++] = a[i++];
    }
    while (j < b.length) {//序列b中多余的元素移入新数组
        result[k++] = b[j++];
    }
    System.out.println(Arrays.toString(result));
    return result;
}
复制代码