活动地址：21天学习挑战赛

文章目录

一、冒泡排序法

1.基本思想

2.算法步骤

3.代码实践

4.复杂度分析

二、直接选择排序法

1.基本思想

2.算法步骤

3.代码实践

4.复杂度分析

---

一、冒泡排序法

1.基本思想

冒泡排序是一种最简单的交换排序方法。其基本思想是：通过两两比较相邻记录的关键字，如果发生逆序则进行交换，从而使关键字小的记录如气泡一般逐渐往上“漂浮”（左移），或者使关键字大的记录如石头一般逐渐往下“坠落”（右移），反复直至序列完全有序为止。

2.算法步骤

1. 设待排序的记录存放在数组r[...n]中。首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序(即L.r[1].key>L.r[2].key), 则交换两个记录。然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称作第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。
2. 然后进行第二趟起泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上。
3. 重复上述比较和交换过程,第i趟是从L.r[1]到L.r[n-i+1]依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。直到在某一趟排序过程中没有进行过交换记录的操作,说明序列已全部达到排序要求,则完成排序。

3.代码实践

public class DayFour {
    public static void main(String[] args) {
        int []a={3,38,5,44,15,36,26,27,2,47,46,4,19,50,48};
        System.out.print("原无序数组为：");
        for (int i = 0; i 
            System.out.print(a[i]+" ");
        }
        System.out.println();
        System.out.print("冒泡排序后：");
        Bubblesort(a);
        for (int i = 0; i 
            System.out.print(a[i]+" ");
        }
 
    }
    private static  void Bubblesort(int[] a){
        //外出循环控制循环趟数，一共n-1趟
        for(int i=0;i1;i++){
            //内层循环控制每一趟比较的次数 共n-1-i次比较
            // 因为前i个元素都已经交换完毕排序好了，得从剩下的不包括本身的n-1-i个元素中两两比较
            for(int j=0;j1-i;j++){
                if(a[j+1]
                    int temp=a[j+1];
                    a[j+1]=a[j];
                    a[j]=temp;
                }
            }
        }
    }
}

 

4.复杂度分析

（1）时间复杂度

最好情况下为正序序列，只需要进行一趟排序，在排序过程中进行n-1次关键字的比较，且不会移动记录；最坏的情况为逆序，需要进行n-1趟排序，总的关键字比较次数和记录移动的次数分别为n^2/2和（3n^2）/2 ;所以在平均情况下，其二者值为n^2/4 和(3n^2)/4

故冒泡排序的时间复杂度为O(n^2)

（2）空间复杂度

因为只有在交换记录值的时候需要一个临时的辅助空间，故冒泡排序的空间复杂度为O(1)

---

二、直接选择排序法

1.基本思想

直接选择排序法也叫简单选择排序法。基本思想是：每一趟从待排序的记录中选出关键字最小的记录，按照顺序放在已经排序的记录序列的最后，直到全部排完为止。

2.算法步骤

1. 设待排序的记录存储在数组r[1...n]中。第一趟从元素r[1]开始，通过n-1次的比较，从n个记录中选出关键字最小的记录，记为r[min]。交换r[1]和r[min]
2. 第二趟从元素r[2]开始，通过n-2次的比较，从n-1个记录中选出关键字最小的记录，记为r[min]，交换r[2]和r[min]
3. 依次类推，第i趟从r[i]开始，通过n-i次的比较，从n-i+1个记录中选出关键字最小的记录，记为r[min]，交换r[ i ]和r[min]
4. 经过n-1趟，排序完成

 

 

3.代码实践

public class DayThree {
    public static void main(String[] args) {
        int []a={5,38,47,15,36,26};
        System.out.print("原无序数组为：");
        for (int i = 0; i 
            System.out.print(a[i]+" ");
        }
        System.out.println();
        System.out.print("直接选择排序后：");
        sort(a);
        for (int i = 0; i 
            System.out.print(a[i]+" ");
        }
    }
    private static void sort(int []a){
        //外层循环控制循环执行的次数
        for(int i=0;i1;i++){
            //假设当前位置i上的元素为最小元素，将其下标i存在min中
            int min=i;
            //内层循环负责在无序区域中找出比当前元素更小的元素并将其下标记录在min中
            for(int j=i+1;j
                if(a[j]
                    min=j;//记录下标
                }
            }
            //如果本轮次选出的最小元素没有在它合适的位置i上则进行交换
            if(min!=i){
                int temp=a[i];
                a[i]=a[min];
                a[min]=temp;
            }
        }
    }
}
 

4.复杂度分析

（1）时间复杂度

直接选择排序过程中，所需进行记录的移动次数较少。

最好的情况是正序序列，那么不需移动任何元素；最坏的情况是逆序序列，需要移动3(n-1)次；但是，无论初始排列的序列如何，所需要进行的关键字间的比较次数相同，均为n^2/2

因此，直接选择排序的时间复杂度为O(n^2)

（2）空间复杂度

同冒泡排序一样，只有在交换记录值的时候需要一个临时的辅助空间，故直接选择排序的空间复杂度为O(1)