内部排序之交换排序
冒泡排序
冒泡排序是很常见的交换排序之一，也是面试中经常问到的一种排序算法。
对于包含n个数据的一组记录，在最坏的情况下，冒泡排序需要进行n-1趟比较。
第一趟：依次比较0和1、1和2、2和3、·······的元素，如果发现第一个数据大于后一个数据，则交换他们。经过第一趟比较，最大的元素排到了最后。
第二趟：依次比较0和1、1和2、2和3、····n-3和n-2处的元素，如果第一个数据大于后一个数据，交换
·········
实际上，冒泡排序的每趟结束后，能够将当前较大的值放到最后面的位置，而且能够理顺前面的元素；如果某趟没有发生交换，可以提前结束排序
冒泡排序十分简单，容易想象理解，下面是java代码：
public class BubbleSort {
public static void bubbleSort(DataWrap[] data) {
System.out.println("开始排序");
int length=data.length;
for (int i = 0; i < length-1; i++) {
boolean flag=false;
for (int j = 0; j < length-1-i; j++) {
//如果j索引处的元素大于j+1索引处的元素
if (data[j].compareTo(data[j+1])>0) {
//交换
DataWrap tmp=data[j+1];
data[j+1]=data[j];
data[j]=tmp;
flag=true;
}
}
System.out.println(Arrays.toString(data));
if (!flag) {
break;
}
}
}
public static void main(String[] args) {
DataWrap[] data={
new DataWrap(9, ""),
new DataWrap(16, ""),
new DataWrap(21, ""),
new DataWrap(23, ""),
new DataWrap(30, ""),
new DataWrap(49, ""),
new DataWrap(21, "*"),
new DataWrap(30, "*")
};
System.out.println("排序前：\n"+Arrays.toString(data));
bubbleSort(data);
System.out.println("排序后：\n"+Arrays.toString(data));
}
}
public class BubbleSort {
public static void bubbleSort(DataWrap[] data) {
System.out.println("开始排序");
int length=data.length;
for (int i = 0; i < length-1; i++) {
boolean flag=false;
for (int j = 0; j < length-1-i; j++) {
//如果j索引处的元素大于j+1索引处的元素
if (data[j].compareTo(data[j+1])>0) {
//交换
DataWrap tmp=data[j+1];
data[j+1]=data[j];
data[j]=tmp;
flag=true;
}
}
System.out.println(Arrays.toString(data));
if (!flag) {
break;
}
}
}
public static void main(String[] args) {
DataWrap[] data={
new DataWrap(9, ""),
new DataWrap(16, ""),
new DataWrap(21, ""),
new DataWrap(23, ""),
new DataWrap(30, ""),
new DataWrap(49, ""),
new DataWrap(21, "*"),
new DataWrap(30, "*")
};
System.out.println("排序前：\n"+Arrays.toString(data));
bubbleSort(data);
System.out.println("排序后：\n"+Arrays.toString(data));
}
}
快速排序
快速排序是一个速度非常快的交换排序方法，基本思路很简单：从待排序的数据序列中任取一个数据作为分界值，所有比它小的元素放在左边，所有比它大的数据放在右边。经过第一次交换，形成左右两个子序列，左边序列中数据元素值比分界值小，右边序列中数据元素值都比分界值大。
接下来对左右两个子序列进行递归，对两个子序列重新选择中心元素并进行调整，直到每个子序列的元素只剩一个，排序完成。
源码如下：
public class QuickSort {
private static void swap(DataWrap[] data,int i,int j) {
DataWrap tmp;
tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
public static void subSort(DataWrap[] data,int start,int end) {
if (start<end) {
//以第一个元素作为分界值
DataWrap base=data[start];
//i从左边开始搜索，搜索大于分界值的元素的索引
int i=start;
//j从右边开始搜索，搜索小于分界值的元素的索引
int j=end+1;
while (true) {
//找到大于分界值的元素的索引，或i已经到了end处
while (i<end&&data[++i].compareTo(base)<=0);
//找到小于分界值的元素的索引，或j已经到了start处
while (j>start&&data[--j].compareTo(base)>=0);
if (i<j) {
swap(data, i, j);
}
else {
break;
}
}
swap(data, start, j);
subSort(data, start, j-1);
subSort(data, j+1, end);
}
}
public static void quickSort(DataWrap[] data) {
subSort(data, 0, data.length-1);
}
public static void main(String[] args) {
DataWrap[] data={
new DataWrap(9, ""),
new DataWrap(16, ""),
new DataWrap(21, ""),
new DataWrap(23, ""),
new DataWrap(30, ""),
new DataWrap(49, ""),
new DataWrap(21, "*"),
new DataWrap(30, "*")
};
System.out.println("排序前：\n"+Arrays.toString(data));
quickSort(data);
System.out.println("排序后：\n"+Arrays.toString(data));
}
}
public class QuickSort {
private static void swap(DataWrap[] data,int i,int j) {
DataWrap tmp;
tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
public static void subSort(DataWrap[] data,int start,int end) {
if (start<end) {
//以第一个元素作为分界值
DataWrap base=data[start];
//i从左边开始搜索，搜索大于分界值的元素的索引
int i=start;
//j从右边开始搜索，搜索小于分界值的元素的索引
int j=end+1;
while (true) {
//找到大于分界值的元素的索引，或i已经到了end处
while (i<end&&data[++i].compareTo(base)<=0);
//找到小于分界值的元素的索引，或j已经到了start处
while (j>start&&data[--j].compareTo(base)>=0);
if (i<j) {
swap(data, i, j);
}
else {
break;
}
}
swap(data, start, j);
subSort(data, start, j-1);
subSort(data, j+1, end);
}
}
public static void quickSort(DataWrap[] data) {
subSort(data, 0, data.length-1);
}
public static void main(String[] args) {
DataWrap[] data={
new DataWrap(9, ""),
new DataWrap(16, ""),
new DataWrap(21, ""),
new DataWrap(23, ""),
new DataWrap(30, ""),
new DataWrap(49, ""),
new DataWrap(21, "*"),
new DataWrap(30, "*")
};
System.out.println("排序前：\n"+Arrays.toString(data));
quickSort(data);
System.out.println("排序后：\n"+Arrays.toString(data));
}
}
补充：软件开发 , Java ,
