数据结构-交换排序

交换排序算法理解与实现

交换排序

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

冒泡排序

算法思想

冒泡排序就是将数组中的数值从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)

快速排序

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

算法思想

首先将待排序记录中的所有记录作为当前待排序区域,从中任选取一个记录(通常选取第一个)作为基准记录,并以该基准记录的关键字值为基准,从位于待排序列左右两端开始,逐渐向中间靠拢,交替与基准记录的额关键字值进行比较,交换。

每次比较,若遇左侧记录的关键字值大于基准记录的关键字值,则将其与基准记录交换,使其移到基准记录的右侧;若遇到右侧记录的关键字值小于基准记录的关键字值,则将其与基准记录交换,使其移到基准记录的左侧。基准记录将待排序记录分成左右两个区域,位于基准记录左侧的关键字值都小于或等于基准记录的关键字值;位于基准记录右侧的关键字值都大于或者等于基准记录的值,把这样一个过程称作一趟快速排序。

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

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