1、排序算法基本概念
1.1、什么是排序算法
所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范,要得到一个符合实际的优秀算法,得经过大量的推理和分析。(摘自百科)
1.2、排序算法稳定性说明
假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。
假定我们拥有一个数据库表,里面记录了学生的出生年份和出生月份,分别记为year和month,我们先按月份将该表中的数据排好序。如下:
year(年份) | month(月份) |
---|---|
1992 | 1 |
1991 | 1 |
1992 | 3 |
1993 | 4 |
1992 | 8 |
1992 | 12 |
此时如果继续按照年份排序,如果选择一个不稳定的排序,可能会导致1992年的原本排序打乱,出现如下结果:
year(年份) | month(月份) |
---|---|
1991 | 1 |
1992 | 3 |
1992 | 1 |
1992 | 12 |
1992 | 8 |
1993 | 4 |
显然不稳定的排序会导致原本的排序被打乱,出现我们不想要的结果。
1.3、排序算法的分类
从是否全部使用内存的角度可以分为:
- 内部排序:只使用内存,常见的算法有插入排序、选择排序、冒泡排序、堆排序、快速排序。
- 外部排序:借助磁盘等辅存,常用于大量数据排序,一次性不能装入内存。常见算法有归并排序、计数排序、基数排序、桶排序。
从使用方法上可以分为:
- 插入:每次插入元素至已有序列,常见有直接插入排序、希尔排序等
- 选择:每次选择最大或最小元素,常见有直接选择排序、堆排序等
- 交换:每次使用交换两个元素的方式,常见有冒泡排序、快速排序等
- 归并:分组后合,常见有并归并排序等
- 其他:基数排序、桶排序等
2、常见排序算法
2.1、插入排序
每次将一个元素插入至一个排好序的序列中。针对一个未排序的数列,我们首先选择首元素,然后遍历,依次插入第2个、第3个…,每次插入元素时从已排好序的元素右边开始比较,如果小于该元素,交换。直至大于被比较元素。
算法时间复杂度
最好:O(n)
平均:O(n^2)
算法空间复杂度:O(1)
稳定性:稳定
算法实现:
/**
* @param datas 待排序序列
*/@Overridepublicvoidsort(int[] datas) {for (int i =1; i < datas.length; i++) {int j = i -1;int sel_num = datas[i];while (j >=0 && sel_num < datas[j]) {
datas[j +1] = datas[j--];
}
datas[j +1] = sel_num;
}
}
2.1、选择排序
每次从待排序序列中选择最小的一个元素。针对一个未排序数列,首先从中选择最小的一个数,然后再从剩下的元素中选择次小的数,直到待排序数列为空。
算法实现:
算法时间复杂度
最好:O(n^2)
平均:O(n^2)
算法空间复杂度:O(1)
稳定性:不稳定
/**
* @param datas 待排序序列
*/publicvoidsort(int[] datas) {for (int i =0; i < datas.length; i++) {int minIndex = i;for (int j = i +1; j < datas.length; j++) {if (datas[minIndex] > datas[j]) {
minIndex = j;
}
}int temp = datas[minIndex];
datas[minIndex] = datas[i];
datas[i] = temp;
}
}
2.3、冒泡排序
针对未排序数列,自下而上的一次比较相邻的两个数,让较小的数排上上面,这样一趟下来,最小的数就会排在第一个,然后重复该操作。
代码实现:
算法时间复杂度
最好:O(n^2),可改进成O(n),算法判断扫描时是否交换过位置
平均:O(n^2)
算法空间复杂度:O(1)
稳定性:稳定
/**
* @param datas 待排序序列
*/publicvoidsort(int[] datas) {for (int i =0; i < datas.length-1; i++) {for (int j = datas.length -1; j > i; j--) {if(datas[j]<datas[j-1]){int temp = datas[j];
datas[j] = datas[j-1];
datas[j-1] = temp;
}
}
}
}
2.4、快速排序
选择一个基准元素,然后用这个元素将待排序数组分成两部分,一部分在左边,都比基准元素小,一部分在右边都比基准元素大。针对左右两边的数列重复该方法。
算法时间复杂度
最好:O(n*log2n)
最坏:O(n^2) 待排序数列已是排好序的
平均:O(n*log2n)
算法空间复杂度:O(n*log2n)
稳定性:不稳定
算法实现1:
/**
* @param datas 待排序序列
* @param start 待排序序列起始位置
* @paramend 待排序序列结束位置
*/public void sort(int[] datas) {
sort(datas,0, datas.length -1);
}private void sort(int[] datas,int start,intend) {if (start <end) {int selNum = datas[start];intleft = start;intright =end;while (right !=left) {while (left <right && selNum < datas[right]) {right--;
}while (left <right && selNum >= datas[left]) {left++;
}int temp = datas[left];
datas[left] = datas[right];
datas[right] = temp;
}
datas[left] = selNum;
sort(datas, start,left -1);
sort(datas,left +1,end);
}
}
算法实现2:
/**
* @param datas 待排序序列
*/publicvoidsort(int[] datas) {
sort(datas,0, datas.length -1);
}/**
* @param datas 待排序序列
* @param start 待排序序列起始位置
* @param end 待排序序列结束位置
*/privatevoidsort(int[] datas,int start,int end) {if(start >= end){return;
}int index = start;int selNum = datas[end];int temp;for (int i = start; i < end ; i++) {if (selNum > datas[i]) {
temp = datas[index];
datas[index] = datas[i];
datas[i] = temp;
index++;
}
}
temp = datas[index];
datas[index] = datas[end];
datas[end] = temp;
sort(datas,start,index-1);
sort(datas,index+1,end);
}
2.5、堆排序
使用完全二叉树保存待排序数列,将该二叉树变成大根堆,然后交换对顶元素和最后一个元素,然后调整使该二叉树回归至大根堆。重复执行直至堆大小为1。
算法实现:
算法时间复杂度
最好:O(n*log2n)
最坏:O(n*log2n)
平均:O(n*log2n)
算法空间复杂度:O(1)
稳定性:不稳定
/**
* @param datas 待排序序列
*/publicvoidsort(int[] datas) {
buildMaxHeap(datas);int len = datas.length;for (int i = len -1; i >0; i--) {
swap(datas,0, i);
maxHeapify(datas,0, i);
}
}/**
* 构建最大堆
* @param datas 待排序序列
*/privatevoidbuildMaxHeap(int[] datas) {int endIndex = parent(datas.length);for (int i = endIndex; i >=0; i--) {
maxHeapify(datas, i, datas.length);
}
}/**
* 调整最大堆,使恢复至最大堆
* @param datas 待排序序列
* @param index 待调整元素位置
* @param heapSize 堆大小
*/privatevoidmaxHeapify(int[] datas,int index,int heapSize) {int indexMax = index;int left = leftChild(index);if ((left +1) <= heapSize && datas[indexMax] < datas[left]) {
indexMax = left;
}int right = rightChild(index);if ((right +1) <= heapSize && datas[indexMax] < datas[right]) {
indexMax = right;
}if (index != indexMax) {
swap(datas, index, indexMax);
maxHeapify(datas, indexMax, heapSize);
}
}privatevoidswap(int[] datas,int i,int j) {int temp = datas[i];
datas[i] = datas[j];
datas[j] = temp;
}/**
* 求元素父元素位置
* @param index 元素位置(从0开始)
*/privateintparent(int index) {return (index +1) /2 -1;
}/**
* 求元素左孩子元素位置
* @param index 元素位置(从0开始)
*/privateintleftChild(int index) {return (index +1) *2 -1;
}/**
* 求元素有孩子元素位置
* @param index 元素位置(从0开始)
*/privateintrightChild(int index) {return (index +1) *2;
}
2.6、归并排序
首先将待排序数列分成两部分,然后遍历将每部分再分为两部分,直至每一部分只包含一个元素,然后在依次将每一部分合并成一个有序数列。
算法时间复杂度
最好:O(n*log2n)
最坏:O(n*log2n)
平均:O(n*log2n)
算法空间复杂度:O(1)
稳定性:稳定
算法实现:
/**
* @param datas 待排序序列
*/publicvoidsort(int[] datas) {
sort(datas,0, datas.length -1);
}/**
* @param datas 待排序序列
* @param start 待排序序列起始位置
* @param end 待排序序列结束位置
*/privatevoidsort(int[] datas,int start,int end) {if (end == start) {return;
}int splitLen = start + (end - start) /2;
sort(datas, start, splitLen);
sort(datas, splitLen +1, end);
merge(datas, start, splitLen, end);
}/**
* @param datas 待排序序列
* @param start 待合并序列起始位置
* @param splitLen 待合并序列中间分隔位置
* @param end 待合并序列结束位置
*/privatevoidmerge(int[] datas,int start,int splitLen,int end) {int i =0, j =0;int[] temp =newint[end - start +1];while (i <= splitLen - start && j <= end - splitLen -1) {if (datas[start + i] <= datas[splitLen +1 + j]) {
temp[i + j] = datas[start + i];
i++;
}else {
temp[i + j] = datas[splitLen +1 + j];
j++;
}
}for (int k = i; k <= splitLen - start; k++) {
temp[k + j] = datas[start + k];
}for (int k = j; k <= end - splitLen -1; k++) {
temp[k + i] = datas[splitLen +1 + k];
}for (int k = start; k <= end; k++) {
datas[k] = temp[k-start];
}
}