冒泡排序和选择排序

2019-11-06 06:20:13

字体：大中小

来源：转载

供稿：网友

Bubble sort：

sometimes referred to as sinking sort, is a simple sorting algorithmthat repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. （from WIKI）

每相邻的两个数比较，大的下沉，小的上浮

Ps: 假设有这样一个数组 int[] a = { a1,a2,a3,a4,a5,a6}；

1 a[0]与a[1] a[1]与a[2] a[2]与a[3] a[3]与a[4] a[4]与a[5] 得到a[5]

2 a[0]与a[1] a[1]与a[2] a[2]与a[3] a[3]与a[4] 得到a[4]

3 a[0]与a[1] a[1]与a[2] a[2]与a[3] 得到a[3]

4 a[0]与a[1] a[1]与a[2] 得到a[2]

5 a[0]与a[1] 得到a[1] over

典型的for循环嵌套，一个控制行（比较的次数），一个控制列数（每次比较需要循环的次数）。为了更直观，贴图一张：By Swfung8-Own work, bubble sort GIF bubbleSort

代码实现：

public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { swap(arr,j,j+1); } } } }

Swap方法：

PRivate static void swap(int[] arr,int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

Select Sort：

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.（from WIKI）

64 25 12 22 11 // this is the initial, starting state of the array11 25 12 22 64 // sorted sublist = {11}11 12 25 22 64 // sorted sublist = {11, 12}11 12 22 25 64 // sorted sublist = {11, 12, 22}11 12 22 25 64 // sorted sublist = {11, 12, 22, 25}11 12 22 25 64 // sorted sublist = {11, 12, 22, 25, 64}

简单来说：

先从数组中找出最小的排列在左侧的sorted sublist，然后在剩下的unsorted element里找出最小的元素添加到左侧的sorted sublist，好比蛇通象最终形成一个有序的数组。

为了更直观，贴图一张，By Joestape89 at the English language Wikipedia, CC BY-SA 3.0, select sort GIF

select sort

代码实现：

private static void selectSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { for (int j = i + 1; j < arr.length; j++) { if (arr[i] > arr[j]) { swap(arr,i,j); } } } }

牵涉到算法的具体分析方面，本人还在fighting中，故不做分析。。。

上一篇：UVa 10891 Game of Sum

下一篇：【九度OJ】题目1438：最小公倍数解题报告