基本思想:在要排序的一组数中,假设前面
(n-1)[n>=2]
个数已经是排好顺序的,现在要把第n
个数插到前面的有序数中,使得这n
个数也是排好顺序的。如此反复循环,直到全部排好顺序。
总体分析:
所以这里肯定要用到嵌套for
循环。
public void insertSort(int[] arr) {
int len = arr.length;
//要插入的数
int insertNum;
//因为第一次不用,所以从1开始
for (int i = 1; i < len; i++) {
insertNum = arr[i];
//序列元素个数
int j = i - 1;
//从后往前循环,将大于insertNum的数向后移动
while (j >=0 && arr[j] > insertNum) {
//元素向后移动
arr[j + 1] = arr[j];
j--;
}
//找到位置,插入当前元素
arr[j + 1] = insertNum;
}
}
针对直接插入排序的下效率问题,有人对次进行了改进与升级,这就是现在的希尔排序。希尔排序,也称递减增量排序算法, 是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是
1959
年由D.L.Shell
提出来的,相对直接插入排序有较大的改进。希尔排序的实质就是分组插入排序,该方法又称缩小增量排序。基本思想:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序, 然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。 因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的. 因此希尔排序在时间效率上比前两种方法有较大提高。步长的选择是希尔排序的重要部分。 只要最终步长为1任何步长序列都可以工作。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
对于直接插入排序问题,数据量巨大时。 将数的个数设为n,取奇数k=n/2,将下标差值为k的数分为一组,构成有序序列。 再取k=k/2 ,将下标差值为k的书分为一组,构成有序序列。 重复第二步,直到k=1执行简单插入排序。
算法最开始以一定的步长进行排序,然后会继续以一定步长进行排序,最终算法以步长为1进行排序。
当步长为1时,算法变为插入排序,这就保证了数据一定会被排序。
Donald Shell
最初建议步长选择为\frac{n}{2}并且对步长取半直到步长达到 1。
虽然这样取可以比\mathcal{O}(n^2)类的算法(插入排序)更好,但这样仍然有减少平均时间和最差时间的余地。
希尔排序示例:n=10的一个数组 58 27 32 93 65 87 58 46 9 65,步长为n/2。
第一次排序 步长为 10/2 = 5
58 27 32 93 65 87 58 46 9 65
1A 1B
2A 2B
3A 3B
4A 4B
5A 5B
首先将待排序元素序列分组,以5为步长,(1A,1B),(2A,2B),(3A,3B)等为分组标记,大写字母表示是该组的第几个元素,
数字相同的表示在同一组,这样就分成5组,即(58,87),(27,58),(32,46),(93,9),(65,65),
然后分别对各分组进行直接插入排序,排序后5组为(58,87),(27,58),(32,46),(9,93),(65,65),
分组排序只是变得各个分组内的下表,下同。
第二次排序 步长为 5/2 = 2
58 27 32 9 65 87 58 46 93 65
1A 1B 1C 1D 1E
2A 2B 2C 2D 2E
第三次排序 步长为 2/2 = 1
32 9 58 27 58 46 65 65 93 87
1A 1B 1C 1D 1E 1F 1G 1H 1I 1J
第四次排序 步长为 1/2 = 0 得到有序元素序列
9 27 32 46 58 58 65 65 87 93
public void shellSort(int[] arr) {
int len = arr.length;
while (len != 0) {
len = len / 2;
//分组
for (int i = 0; i < len; i++) {
//元素从第二个开始
for (int j = i + len; j < arr.length; j += len) {
//k为有序序列最后一位的位数
int k = j - len;
//要插入的元素
int temp = arr[j];
//从后往前遍历
while (k >= 0 && temp < arr[k]) {
arr[k + len] = arr[k];
//向后移动len位
k -= len;
}
arr[k + len] = temp;
}
}
}
}
基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换; 然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。
思路:
public void selectSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len; i++) {
int value = arr[i];
int position = i;
//找到最小的值和位置
for (int j = i + 1; j < len; j++) {
if (arr[j] < value) {
value = arr[j];
position = j;
}
}
//进行交换
arr[position] = arr[i];
arr[i] = value;
}
}
对简单选择排序的优化。 基本思想:堆排序是一种树形选择排序,是对直接选择排序的有效改进。
堆(heap)
,这里所说的堆是数据结构中的堆,而不是内存模型中的堆。堆数据结构是一种特殊的二叉树,在这棵树中,所有父节点都满足大于等于其子节点的堆叫大根堆,所有父节点都满足小于等于其子节点的堆叫小根堆。堆虽然是一颗树,但是通常存放在一个数组中,父节点和孩子节点的父子关系通过数组下标来确定。如下图的小根堆及存储它的数组:
堆的介绍:
由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项(大顶堆)。完全二叉树可以很直观地表示堆的结构。堆顶为根,其它为左子树、右子树。 初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储序,使之成为一个堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。 然后对前面(n-1)个数重新调整使之成为堆。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。 从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。
步骤:
public void heapSort(int[] arr) {
int len = arr.length;
//循环建堆
for (int i = 0; i < len - 1; i++) {
//建堆
buildMaxHeap(arr, len - 1 - i);
//交换堆顶和最后一个元素
swap(arr, 0, len - 1 - i);
}
}
//交换方法
private void swap(int[] data, int i, int j) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
//对data数组从0到lastIndex建大顶堆
private void buildMaxHeap(int[] data, int lastIndex) {
//从lastIndex处节点(最后一个节点)的父节点开始
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
//k保存正在判断的节点
int k = i;
//如果当前k节点的子节点存在
while (k * 2 + 1 <= lastIndex) {
//k节点的左子节点的索引
int biggerIndex = 2 * k + 1;
//如果biggerIndex小于lastIndex,即biggerIndex+1代表的k节点的右子节点存在
if (biggerIndex < lastIndex) {
//若果右子节点的值较大
if (data[biggerIndex] < data[biggerIndex + 1]) {
//biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
//如果k节点的值小于其较大的子节点的值
if (data[k] < data[biggerIndex]) {
//交换他们
swap(data, k, biggerIndex);
//将biggerIndex赋予k,开始while循环的下一次循环,重新保证k节点的值大于其左右子节点的值
k = biggerIndex;
} else {
break;
}
}
}
}
步骤:
public void bubbleSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
基本思想:找出一个元素(理论上可以随便找一个)作为基准
(pivot)
,然后对数组进行分区操作, 使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置。 递归快速排序,将其他n-1
个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置,排序完成。 所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
partition
算法是快速排序的核心,在学习快排之前,可以先学习一下这个算法。下面先贴代码:
public int partition(int[] num, int left, int right) {
if (num == null || num.length <= 0 || left < 0 || right >= num.length) {
return 0;
}
//获取数组中间元素的下标
int prio = num[left + (right - left) / 2];
//从两端交替向中间扫描
while (left <= right) {
while (num[left] < prio)
left++;
while (num[right] > prio)
right--;
if (left <= right) {
//最终将基准数归位
swap(num, left, right);
left++;
right--;
}
}
return left;
}
这个方法的思路是先找一个枢纽元(这个方法实现里面找的是第一个元素,具体其实大有文章不过这里先简化描述),
再从数组的两边(具体从哪里到哪里由传进来额参数决定)生成两个指针left
和right
,
每次发现左边的元素大于枢纽元则i停下来,右边的元素小于枢纽元j就停下来,并且交换这个两个数的位置。
直到两个指针left
,right
相遇。再把枢纽元插入left
的位置,也就是它应该在的位置。
这么做最后的结果是让数组的[left,right]
部分呈现出2部分,枢纽元最终位置以左都是小于等于枢纽元的,以右都是大于等于枢纽元的。而枢纽元则被插入到了一个绝对正确的位置。
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
int[] data = new int[]{26, 53, 67, 48, 57, 13, 48, 32, 60, 50};
quickSort(data,0,data.length-1);
}
void quickSort(int arr[], int left, int right) {
if (left < right) {
//算出枢轴值
int index = partition(arr, left, right);
//对低子表递归排序
quickSort(arr, left, index - 1);
//对高子表递归排序
quickSort(arr, index + 1, right);
}
for (int i = 0; i < arr.length; i++) {
Log.e("@@@", "" + arr[i]);
}
}
public int partition(int[] num, int left, int right) {
if (num == null || num.length <= 0 || left < 0 || right >= num.length) {
return 0;
}
int prio = num[left + (right - left) / 2]; //获取数组中间元素的下标
while (left <= right) { //从两端交替向中间扫描
while (num[left] < prio)
left++;
while (num[right] > prio)
right--;
if (left <= right) {
swap(num, left, right); //最终将基准数归位
left++;
right--;
}
}
return left;
}
public void swap(int[] num, int left, int right) {
int temp = num[left];
num[left] = num[right];
num[right] = temp;
}
速度仅次于快速排序,内存少的时候使用,可以进行并行计算的时候使用。 归并(
Merge
)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列, 每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
{
int[] data = new int[]{26, 53, 67, 48, 57, 13, 48, 32, 60, 50};
data = mergeSort(data, 0, data.length - 1);
for (int i = 0; i < data.length; i++) {
Log.e("@@@", "" + data[i]);
}
}
public static int[] mergeSort(int[] a, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
mergeSort(a, low, mid);
mergeSort(a, mid + 1, high);
//左右归并
merge(a, low, mid, high);
}
return a;
}
public static void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;
int j = mid + 1;
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = a[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = a[j++];
}
// 把新数组中的数覆盖nums数组
for (int x = 0; x < temp.length; x++) {
a[x + low] = temp[x];
}
}
基数排序
(radix sort)
又称桶排序(bucket sort)
,相对于常见的比较排序,基数排序是一种分配式排序, 即通过将所有数字分配到应在的位置最后再覆盖到原数组完成排序的过程
用于大量数,很长的数进行排序时。
基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始, 依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
我们回想一下我们小时候是怎么学习比较数字大小的?我们是先比位数,如果一个位数比另一个位数多,
那这个数肯定更大。如果位数同样多,就按位数递减依次往下进行比较,哪个数在这一位上更大那就停止比较,
得出这个在这个位上数更大的数字整体更大的结论。当然我们也可以从最小的位开始比较,
这其实就对应了基数排序里的MSD(most significant digital)和LSD(least significant digital)
两种排序方式。
想清楚了这一点之后,我们就要考虑如何存储每一位排序结果的问题了,首先既然作为分配式排序,联想计数排序,
每一位排序时存储该次排序结果的数据结构应该至少是一个长度为10的数组(对应十进制该位0-9的数字)。
同时可能存在以下情况:原数组中所有元素在该位上的数字都相同,那一维数组就没法满足我们的需要了,
我们需要一个10*n
(n
为数组长度)的二维数组来存储每次位排序结果。
熟悉计数排序结果的读者可能会好奇:为什么不能像计数排序一样,在每个位置只存储出现该数字的次数, 而不存储具体的值,这样不就可以用一维数组了?这个我们不妨先思考一下,在对基数排序分析完之后再来看这个问题。 现在我们可以存储每次位排序的结果了,为了在下一位排序前用到这一位排序的结果, 我们要将桶里排序的结果还原到原数组中去,然后继续对更改后的原数组执行前一步的位排序操作,如此循环, 最后的结果就是数组内元素先按最高位排序,最高位相同的依次按下一位排序,依次递推。得到排序的结果数组。
初始化:构造一个10*n
的二维数组,一个长度为n的数组用于存储每次位排序时每个桶子里有多少个元素。
循环操作:从低位开始(我们采用LSD
的方式),将所有元素对应该位的数字存到相应的桶子里去(对应二维数组的那一列)。
然后将所有桶子里的元素按照桶子标号从小到大取出,对于同一个桶子里的元素,先放进去的先取出,
后放进去的后取出(保证排序稳定性)。这样原数组就按该位排序完毕了,继续下一位操作,直到最高位排序完成。
private static void radixSort(int[] array,int d) {
int n=1;//代表位数对应的数:1,10,100...
int k=0;//保存每一位排序后的结果用于下一位的排序输入
int length=array.length;
int[][] bucket=new int[10][length];//排序桶用于保存每次排序后的结果,这一位上排序结果相同的数字放在同一个桶里
int[] order=new int[length];//用于保存每个桶里有多少个数字
while(n<d) {
for(int num:array) //将数组array里的每个数字放在相应的桶里 {
int digit=(num/n)%10;
bucket[digit][order[digit]]=num;
order[digit]++;
}
//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
for(int i=0;i<length;i++) {
//这个桶里有数据,从上到下遍历这个桶并将数据保存到原数组中
if(order[i]!=0) {
for(int j=0;j<order[i];j++) {
array[k]=bucket[i][j];
k++;
}
}
order[i]=0;//将桶里计数器置0,用于下一次位排序
}
n*=10;
k=0;//将k置0,用于下一轮保存位排序结果
}
}
public static void main(String[] args) {
int[] A=new int[]{73,22, 93, 43, 55, 14, 28, 65, 39, 81};
radixSort(A, 100);
for(int num:A) {
System.out.println(num);
}
}
总结:
n/2
开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1
, n/2-2
, …这些父节点选择元素时,有可能第n/2
个父节点交换把后面一个元素交换过去了,而第n/2-1
个父节点把后面一个相同的元素没有交换,所以堆排序并不稳定。