java数据结构与算法—简单排序（冒泡、选择、插入）

忘是亡心i 2022-05-27 08:36 113阅读 0赞

本节目标：

1.掌握冒泡排序的原理与操作

2.掌握选择排序的原理与操作

3.掌握插入排序的原理与操作

# 冒泡排序 #

/\*\*  
 \* 冒泡排序  
 \* @author root  
 \*  
 \*/  
public class BubbleSort \{  
public static void sort(int\[\] arr) \{  
int temp;// 中间临时变量  
for (int i = 0; i < arr.length - 1; i++) \{//定义外层循环，从下标0-（最大下标-1）遍历  
for (int j = arr.length - 1; j > i; j--) \{//定义内层循环，以最大下标至外层循环下标前一个下标的范围，从后往前遍历  
if (arr\[j\] < arr\[j - 1\]) \{//从后往前遍历的过程中，如果前一个元素比后一个元素大，前后元素调换位置-->将最小的元素“冒泡”到该层循环对应的外层循环的下标位置。  
temp = arr\[j\];  
arr\[j\] = arr\[j - 1\];  
arr\[j - 1\] = temp;  
\}  
\}  
\}  
  
  
\}

时间复杂度：

当最好的情况，也就是要排序的序列本身就是有序的，需要进行（n-1）次比较，没有数据交换，时间复杂度为O(n).   
当最坏的情况，即待排序的表是逆序的情况，此时需要比较次数为：1+2+3+…+(n-1)=n(n-1)/2 次，并作等数量级的记录移动，因此总的时间复杂度为O(n^2)

# 选择排序 #

/\*\*  
 \* 选择排序  
 \* @author root  
 \*  
 \*/  
public class SelectionSort \{  
public static void sort(int\[\] arr)\{  
int temp;  
for (int i = 0; i < arr.length-1; i++) \{//定义外层循环，从下标0-（最大下标-1）遍历  
int k = i;//下标标志位，标志最小元素的下标，从最外层循环的下标开始。  
for (int j = i; j < arr.length; j++) \{//定义内层循环，下标从外层循环的下标开始，到最大下标为止，遍历元素进行比较  
if (arr\[j\] < arr\[k\]) \{//在内层循环遍历过程中，如果发现有元素小于标志位元素，将该元素的下标设为标志位--->最终标志位结果为内层循环的最小元素下标  
k = j;  
\}  
\}  
temp = arr\[i\];//将每次内循环标志位处的元素与外层循环下标开始处的元素互换。  
arr\[i\] = arr\[k\];  
arr\[k\] = temp;  
\}  
\}

时间复杂度：

选择排序的时间复杂度为O(n^2)，由于每次选择仅考虑某一位置上的数据情况，可能会破坏之前数据的相对位置，因此它是一种不稳定的排序方法。

# 插入排序 #

/\*\*  
 \* 插入排序  
 \* @author root  
 \*/  
public class InsertSort \{  
public static void sort(int\[\] arr) \{  
int i,j,temp;  
        for( i = 1; i< arr.length; i++) \{  
             temp = arr\[i\];//待插入的元素，用临时变量表示  
            for( j = i; j>0 && arr\[j-1\] > temp; j--) \{//内循环，从后往前，与前面已排好序的元素比较，如果大于待插入元素，前面排好序的元素依次后移一位，直到找出可以插入的位置。  
                arr\[j\] = arr\[j-1\];  
            \}  
            arr\[j\] = temp;//插入元素  
        \}  
    \}  
\}

时间复杂度：

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。

最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。

最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。