数据结构-交换排序

交换排序算法理解与实现

交换排序

交换排序的基本思想:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。

冒泡排序

算法思想

冒泡排序就是将数组中的数值从0开始,进行两两比较,若前者大于后者,则交换两个数据元素,一个轮回后,就使最大的值放在了最后面。然后继续从0开始比较,将次大的数值放到第二个位置,一直到排序结束。当然,有可能在进行一部分的时候就有序了,就不用继续排了,注意看代码处理。应为这个过于简单,就不详细说了。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] bubbleSort(int[] data){
boolean exchange; //交换标志
for(int i=1;i<data.length;i++){
exchange = false;
for(int j=0;j<data.length-i;j++){
if(data[j]>data[j+1]){
int tmp = data[j];
data[j] = data[j+1];
data[j+1] = tmp;
exchange = true;
}
}
if(!exchange) break;
}
return data;
}

时间复杂度:O(n2)

快速排序

快速排序采用了分治法策略,分治法的基本思想:将原问题分解成若干个规模更小但结构与原问题相似的子问题。递归地解决这些子问题,然后将这些子问题的解组合成原问题的解。该排序算法是对递归算法的一种改进。

算法思想

首先将待排序记录中的所有记录作为当前待排序区域,从中任选取一个记录(通常选取第一个)作为基准记录,并以该基准记录的关键字值为基准,从位于待排序列左右两端开始,逐渐向中间靠拢,交替与基准记录的关键字值进行比较,交换。这里要设置左右两个标记,分别位于待排序区域两侧,先移动左标记,寻找第一个大于基准的值;然后移动右标记,寻找第一个小于基准的值,若能够找到且此时左标记仍然小于右标记,则交换这两个位置的值,然后继续按照上面的顺序移动左右标记,符合条件时进行交换,直到左标记等于右标记(当前位置的前一个位置元素一定小于基准,且当前位置一定大于基准),此时,就将前一个位置的元素与基准进行交换。

等交换完成后,基准记录将待排序记录分成左右两个区域,位于基准记录左侧的关键字值都小于或等于基准记录的关键字值;位于基准记录右侧的关键字值都大于或者等于基准记录的值,把这样一个过程称作一趟快速排序。

一趟快速排序之后,在分别对基准记录左右两个区域进行快速排序,以此类推,直到每个分区都只有一个记录为止。此时,整个待排序记录按关键字的值有序排列,排序结束。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.Arrays;

public class QuickSort {
public static void main(String[] args) {
//定义数组
int[] data = {30,80,45,61,70,25,49,30,90};
//打印当前数组
System.out.println(Arrays.toString(data));
//进行快速排序
quickSort(data);
//打印排序后的数组
System.out.println(Arrays.toString(data));
}
public static void quickSort(int[] arr) {
int low = 0;
int high = arr.length-1;
quickSort(arr,low,high);
}
//重载快速排序方法进行排序
private static void quickSort(int[] arr, int low, int high) {
if(low<high){
//进行单次排序,找到第一个分界点
int index = onceSort(arr,low,high);
//进行左侧排序
quickSort(arr,low,index-1);
//进行右侧排序
quickSort(arr,index+1,high);
}
}
//单趟数据重排 一次分区操作 把基准放在应该放的地方
private static int onceSort(int[] arr,int low,int high){
int i = low;
int j = high;
//选择基准 这里选择左侧第一个
int x = arr[low];
while(i<j){
//先移动j指针 找小于基准的第一个数
while(arr[j]>=x &&i<j){
j--;
}
//交换基准与从原始j开始第一个小于基准的值
if(i<j){
arr[i] = arr[j];
i++;
}
//再移动i指针 找大于基准的第一个数
while(arr[i]<=x && i<j){
i++;
}
//交换
if(i<j){
arr[j] = arr[i];
j--;
}
}
//i==j时将数据传入 下面的参数中i,j都可以
arr[i] = x;
return i;
}
}

时间复杂度:平均为O(nlog2n),但比较容易收到选取值的影响,因此不够稳定。

您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------