首页 > 嗟来之食 > 交换排序 – klguang –
2016
08-04

交换排序 – klguang –

交互排序思想:在待排序的序列中选择两个记录,将他们的关键码进行比较。如果反序则交互它们的位置。 冒泡排序 基本思想:将序列分为有序区,无序区。每次从无序区冒泡一个最小的记录。 冒泡过程:从无序区从后往前扫描,两个相邻记录比较,如果后面比前面的小,则交互。 算法分析 冒泡排序-java实现 /**
* 将序列分为两部分:有序区:无序区 <br>
* 每趟从无序区 冒泡一个最小的,有序区+1.
* 稳定的排序
*
* @param arr
*/
public static void bubble_normal(int[] arr) {
int size = arr.length;
for (int i = 0; i < size – 2; i++) { //n-1轮冒泡
for (int j = size – 1; j > i; j–) {
if (arr[j] < arr[j – 1]) // 从后往前,小的记录往前冒泡
MathUtil.swap(arr, j, j – 1);
}
System.out.println("第 " + (i + 1) + "轮 :" + Arrays.toString(arr));
}
}

冒泡排序的变体 /**
* 非冒泡排序,也非选择排序,姑且叫他假冒泡<br>
* 将序列分为两部分:有序区:无序区<br>
* 每轮排序从无序区找到一个最小记录,无序区长度-1<br>
*
* 找到一个最小记录的过程:<br>
* 用无序区的第一个元素存储最小记录。<br>
* 对比交换:最小记录>无序区记录就交换<br>
* 纪录在排序过程中的移动不是冒泡,而是跳跃的交换。不稳定的排序<br>
*
* 缺点:本来位于前面的较小数被交换到后面
*
* @param arr
*/
public static void bubble_fake(int[] arr) {
int size = arr.length;
for (int i = 0; i < size – 2; i++) {//n-1轮
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[i]) //确保arr[i]为无序区最小的
MathUtil.swap(arr, i, j);
}
System.out.println("第 " + (i+1) + "轮 :" + Arrays.toString(arr));
}
}
/**
* 冒泡算法的改进,增加isSwaped标志<br>
* 在一轮循环中记录没有交互,也就表明序列已经有序的。<br>
* 当记录交换(冒泡)则isSwaped=true;说明无序。<br>
* @param arr
*/
public static void bubble_optimize(int[] arr) {
int size = arr.length;
boolean isSwaped = true;
for (int i = 0; i < size – 2 && isSwaped; i++) {//n-1轮
isSwaped = false; // 重置状态
for (int j = size – 1; j > i; j–) {
if (arr[j] < arr[j – 1]) { // 从后往前,小的记录往前冒泡
MathUtil.swap(arr, j, j – 1);
isSwaped = true; // 改变则赋值true
}
System.out.println("\t" + Arrays.toString(arr));
}
System.out.println("isChanged:" + isSwaped);
System.out.println("第 " + (i + 1) + "轮 :" + Arrays.toString(arr));
}
}

快速排序
基本思想:选择一个轴值,将待排序列分为两个部分,左侧记录均小于轴值,右侧记录均大于轴值。
划分过程:头尾两根指针分别指向划分区间的头尾,分别向中间靠拢。
过程中,如果尾针所指的记录<轴值,交互,头指针所指记录>轴值,交互。这样就保证了轴值前的所有记录都小于轴值,轴值之后的记录都大于轴值。
直到两根指针相遇的位置,即轴值的最终位置。完成划分。
排序过程:将序列一次划分后,分别对两个子序列进行划分(递归处理),直到划分区间<1 。
一次划分图示:

算法分析

快速排序-java实现 /**
* 划分区间:arr[first]~arr[end]<br>
* 右侧扫描:直到 尾指针 指向的记录 小于 轴值,交互,头指针+1。<br>
* 左侧扫描:直到 头指针 指向的记录 大于 轴值,交互,尾指针-1。<br>
* 头尾两根指针相遇,完成划分。<br>
*
* @param arr
* @param first 划分区间的头指针
* @param end 划分区间的头指针
* @return
*/
public static int partition(int[] arr, int first, int end) {
while (first < end) {//头尾指针相遇,退出循环,即为最终的轴值记录的位置
while (first < end && arr[first] < arr[end])// 右侧扫描
end–;
if (first < end) {
MathUtil.swap(arr, first, end);// 较小记录交互到前面
first++;
}
//具有操作的对称性
while (first < end && arr[first] < arr[end])// 左侧扫描
first++;
if (first < end) {
MathUtil.swap(arr, first, end);// 较大记录交互到后面
end–;
}
}
return first;
}
/**
* 将序列一次划分后,分别对两个子序列进行划分(递归处理),直到划分区间<1 <br>
* @param arr
* @param first
* @param end
*/
public static void quickSort(int[] arr,int first, int end){
if(first<end){//区间长度<1,递归结束
int pivot=partition(arr, first, end);
quickSort(arr, first, pivot – 1);//递归对左侧子序列进行快排
quickSort(arr, pivot + 1, end); //递归对右侧子序列进行快排
}
}

public static void qsort(int[] arr){
quickSort(arr, 0, arr.length-1);
}

最后编辑:
作者:
这个作者貌似有点懒,什么都没有留下。

留下一个回复