交换排序是指比较两个元素的值,不满足要求便把两元素的值交换,重复完成这样的操作达到排序的目的。交换排序包括冒泡排序和快速排序。
冒泡排序
冒泡排序是排序算法中较简单的一个排序。同交换排序的定义一样,它重复遍历所有排序元素,一次比较两个元素,如果顺序不对,则交换两元素,直到所有元素排序完成。
public static int[] BubbleSort(int[] data){
if(data == null || data.length < 2){
return data;
}
for(int i = 0; i < data.length; i++){
for(int j = i+1;j<data.length;j++){
if(data[i] > data[j]){
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}
return data;
}
快速排序
快速排序采用分治的思想,在冒泡排序的基础上改进而来的,冒泡排序每次比较、交换两个元素,而快速排序是跳跃的交换,交换距离很大,因此比较和交换的次数减少,速度也就快了。
具体思想:首先在所有排序元素中找到一个基准元素,接下来需要把排序元素中小于基准元素的元素移动到待排序元素的左边(若排序顺序为从小到大),大于基准元素的值移动到待排序元素的右边。这样,左右两边的元素相对有序,并且确定基准元素的最终排序位置。接着在对左右的元素分别按照上面的方法找去基准元素,移动,直到各个分区只有一个数为之。
public static void QuickSort(int[] data,int begin,int end){
if(begin < end && begin > -1 && end < data.length){
int i = begin;
int j = end;
int temp = data[begin];
while(i < j){
while(j > i && data[j] > temp){
j--;
}
if(data[j] < temp){
data[i] = data[j];
i++;
}
while(i < j && data[i] <= temp){
i++;
}
if(data[i] > temp){
data[j] = data[i];
j--;
}
data[i] = temp;
QuickSort(data,begin,i-1);
QuickSort(data,i+1,end);
}
}
}
转载请注明原文地址: https://ju.6miu.com/read-50382.html