排序按时间复杂度和空间复杂度可分为 低级排序 和 高级排序 算法两种。下面将对排序算法进行讲解,以及样例的展示。
低级排序:冒泡排序、选择排序、插入排序。
冒泡排序:
核心思想,小的数往前移。假设最小的数在最后一位,将最后一位一步步移到第一位。
public void bubbleSort(int[] list) {
int n = list.length - 1;
for(int i = 0; i < n; i ++) {
for(int j = 0; j < n - i; j ++) {
if(list[j] > list[j + 1])
swap(j, j + 1, list);
}
}
}
public void swap(int i, int j, int[]list) {
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}
选择排序:
选择最小数按顺序排列。从当前未排序的数组中,找出一个最小的数,放在第一位。第二小的放在第二位······
public void selectSort(int[] list) {
int min; //记录最小下标
for(int i = 0; i < list.length - 1; i ++) { //对n个数排序,只需将n-1个数排好序,就ok了。所以循环条件是list.length-1.
min = i;
for(int j = i + 1; j < list.length; j ++) { //循环一次找出一个最小数
if(list[j] < list[min]) {
min = j;
}
}
swap(i, min, list);
}
}
public void swap(int i, int j, int[]list) {
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}
插入排序:
取出元素,从后往前依次比较前面的元素。直到前面的数比自己小,则插入到当前位置。在此过程中,大于或等于自己的元素一直往后移位。
public void insertSort(int[] list) {
int sign, temp; // sign记录空值下标,temp记录取出值
for(int i = 1; i < list.length; i ++) {
temp = list[i];
sign = i;
//如果取出值小于前一个值,则把前一个值往后移,覆盖当前值
while(sign > 0 && list[sign - 1] > temp) {
list[sign] = list[sign - 1];
sign --;
}
list[sign] = temp;
}
}
插入排序优化写法:
//优化插入:将数组第一个元素用来保存数据,达到减少比较次数
public void insertSort_2(int[] list) {
int sign, temp; // sign记录空值下标,temp记录取出值
for(int i = 2; i < list.length; i ++) {
temp = list[i];
list[0] = temp;
sign = i - 1;
//如果取出值小于前一个值,则把前一个值往后移,覆盖当前值
while(list[sign] > temp) {
list[sign + 1] = list[sign];
sign --;
}
list[sign + 1] = temp;
}
}
高级排序:快速排序、归并排序。
快速排序:
最流行的排序算法、速度最快的排序算法。选定一个枢轴,小于枢轴的数放左边,大于枢轴的数放右边,交换枢轴两边的数。
public void quickSort(int left, int right, int[] list) {
//选枢轴进行划分
if(left < right) {
int i = left;
int j = right + 1;
int privot = list[left]; //定义一个枢轴
do{
do{
i ++;
}while(list[i] < privot);//找到一个比枢轴大的数
do{
--j;
}while(list[j] > privot);//找到一个比枢轴小的数
if(i<j) swap(i, j, list);
}while(i < j); swap(left, j, list); //将基准数放置到中间 quickSort(left, j - 1, list);
quickSort(j + 1, right, list);
}
}
public void swap(int i, int j, int[]list) {
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}
归并排序:
将两个排好序的数组合并在一起,并且重新排序。比如1->2>3 、1->4->5 合并在一起后就是:1->2>3 ->1->4->5 排好序为:1->1->2->3->4->5. 在此演示的示例为直接合并的数组。
首先,为方便写程序,数组第一个元素将废弃使用,不对其进行排序。
基础归并函数:归并两个排序的数组
public void Merge(int[] initList, int[] mergeList, int l, int m, int n) {
// initList 初始化数组, mergeList存放排好序的数组。
// l表示第一个数组下标,m表示第一个数组最后一个元素下标,n表示第二个数组最后一个元素下标。result表示新建数组下标
int i1, i2, result;
for(i1 = l, i2 = m + 1, result = i1; i1 <= m && i2 <= n; result ++) {
if(initList[i1] <= initList[i2]) {
mergeList[result] = initList[i1];
i1 ++;
}else {
mergeList[result] = initList[i2];
i2 ++;
}
}
// 将第一个数组和第二个数组未放进mergeList的元素复制到mergeList中。(如果没有剩余元素,则复制元素个数为0,不产生影响,所以可以放心对两个数组都进行剩余元素复制)
System.arraycopy(initList, i1, mergeList, result, m - i1 + 1);
System.arraycopy(initList, i2, mergeList, result, n - i2 + 1);
}
其次,有了前面的基础归并函数,那么就可以实现乱序数组的归并排序。其思想,进行多次基础归并。
实现单次归并:划分数组进行归并。第一次单个元素作为划分对象,第二次两个元素作为划分对象·········
public void MergePass(int[] initList, int[] mergeList, int n, int s) { // n表示初始化数组最后一位元素下标,s表示第几次归并。
int i;
for(i = 1; i <= n - 2*s + 1; i += 2*s) { //对划分的数组两两归并
Merge(initList, mergeList, i, i + s - 1, i + 2*s - 1);
} if((i + s - 1) < n) { //有剩余未归并的元素则进行归并
Merge(initList, mergeList, i, i + s - 1, n);
}else { //将剩余元素拷贝下来
System.arraycopy(initList, i, mergeList, i, n + 1 - i);
}
}
最后通过控制归并次数,真正达到乱序数组归并排序的效果:
public void MergeSort(int[] list) {
int[] newList = new int[list.length]; for(int i = 1; i < list.length; i *= 2) {
MergePass(list, newList, list.length - 1, i);
i *= 2; //只所以在此进行i*2,是因为归并后的结果放在newList里面,重新进行归并时。省掉将newList重新拷贝到list的麻烦
MergePass(newList, list, list.length - 1, i);
}
}
接下来,来个归并算法的全家桶吧:
public class MergeSort {
@Test
public void fun() {
int[] a = {0, 23, 47, 81, 95, 7, 14, 39, 55, 62, 74};
MergeSort(a);
for(int i : a) {
System.out.print(i + "\t");
}
}
public void Merge(int[] initList, int[] mergeList, int l, int m, int n) {
// l表示第一个数组下标,m表示最后一个数组下标,result表示新建数组下标
int i1, i2, result;
for(i1 = l, i2 = m + 1, result = i1; i1 <= m && i2 <= n; result ++) {
if(initList[i1] <= initList[i2]) {
mergeList[result] = initList[i1];
i1 ++;
}else {
mergeList[result] = initList[i2];
i2 ++;
}
}
System.arraycopy(initList, i1, mergeList, result, m - i1 + 1);
System.arraycopy(initList, i2, mergeList, result, n - i2 + 1);
}
public void MergePass(int[] initList, int[] mergeList, int n, int s) {
int i;
for(i = 1; i <= n - 2*s + 1; i += 2*s) {
Merge(initList, mergeList, i, i + s - 1, i + 2*s - 1);
} if((i + s - 1) < n) {
Merge(initList, mergeList, i, i + s - 1, n);
}else {
System.arraycopy(initList, i, mergeList, i, n + 1 - i);
}
}
public void MergeSort(int[] list) {
int[] newList = new int[list.length];
for(int i = 1; i < list.length; i *= 2) {
MergePass(list, newList, list.length - 1, i);
i *= 2;
MergePass(newList, list, list.length - 1, i);
}
}
}