冒泡排序、选择排序、直接插入排序

冒泡排序

思想： 不断地从头到尾的比较前后两个数

• 如果前面的数大于后面的数，则执行交换两个元素，然后继续往后比较
• 如果前面的数小于或等于后面的数，则直接往后继续比较

每一次冒泡的过程都会将当前数组的最大值放到当前数组的最后一个位置。 因此，通过为了减少比较的次数。每次冒泡排序数组的长度都是上一轮数组长度减一。

时间复杂度：
冒泡过程需要比较$N$N次，如果数组本身就是有序的，那么每次只需要比较一次，不执行交换。因此，最好时间复杂度为$O(N * 1) = O(N)$O(N∗1)=O(N)。最坏情况是每次都是执行当前数组长度次数的交换，即将首部元素放到数组的最后一个位置， 因此，最坏时间复杂度为$O(N * N) = O(N ^ 2)$O(N∗N)=O(N2)

空间复杂度：

排序过程不申请额外的空间，因此空间复杂度为O(1)

稳定性：
如果两个元素相等，那么冒泡过程不执行交换操作，因此谁在前谁在后都是一样的。因此，冒泡排序是稳定的。

Java代码实现：

public class Code_00_BubbleSort {

	public static void bubbleSort(int[] arr) {
		// 边界条件
		if (arr == null || arr.length < 2) {
			return;
		}
		// 外循环表示的是当前待排序数组的最后一个元素的位置，从N - 1 一直到 1
		// 因为一个数不需要排序，因此边界条件为 e > 0
		for (int e = arr.length - 1; e > 0; e--) {
			// 待排序数组的范围 0 ~ e
			for (int i = 0; i < e; i++) {
				// 如果当前数比后面的数大就执行交换操作
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 1);
				}
			}
		}
	}

	// 执行元素交换操作的函数
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

Python代码实现

def bubble_sort(nums):
    l = len(nums)
    for i in range(0, l - 1):
        flag = True
        for j in range(0, l - i):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                flag = False
        print('index: {} -- {}'.format(i, nums))
        
        # flag用于标记当前轮是否有元素的交换执行
        if flag == True:
            return nums

    return nums

if __name__ == "__main__":
    nums = [5, 2, 9, 7, 6, 12, 3, 4]

    # 冒泡排序
    print('-' * 20)
    print ('bubble sort result is: ', bubble_sort(nums))

---

选择排序

思想： 选择排序是将当前元素和之后数组中最小的元素进行比较

• 如果当前元素大于后面数组中最小的元素，那么执行交换操作
• 如果当前元素小于等于后面数组中最小的元素，则不执行交换操作，继续往后比较
  

时间复杂度：

最好时间复杂度为$O(N)$O(N)，最坏时间复杂度为$O(N^2)$O(N2)

空间复杂度：

$O(1)$O(1)

稳定性:

不稳定，例如5 8 5 2 9，第一轮选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了

Java代码实现：

public class SelectionSort {

	public static void selectionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		// 当前元素位置
		for (int i = 0; i < arr.length - 1; i++) {
			// 首先将当前元素默认为最小元素
			int minIndex = i;
			// 遍历当前位置后的数组，寻找数组中的最小元素
			for (int j = i + 1; j < arr.length; j++) {
				minIndex = arr[j] < arr[minIndex] ? j : minIndex;
			}
			// 执行交换
			swap(arr, i, minIndex);
		}
	}

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

Python代码实现：

# 选择排序
# 每一轮都将当前最小的元素放在已排序区间的后面
def select_sort(nums):
    n = len(nums)
    for i in range(0,n - 1):
        min = i                             #最小元素下标标记
        for j in range(i + 1,n):
            if nums[j] < nums[min] :
                min = j                     #找到最小值的下标
        nums[min],nums[i] = nums[i],nums[min]   #交换两者
        print('index: {} -- {}'.format(i, nums))
    return nums

    
if __name__ == "__main__":
    nums = [5, 2, 9, 7, 6, 12, 3, 4]

    # 选择排序
    print ('select sort result is: ', select_sort(nums))

---

直接插入排序

思想：插入排序就是要每一轮排序都要将当前元素插入到一个已经有序的数组中。将当前元素和有序数组的最后一个元素进行比较

• 如果当前元素大于最后一个元素，笔试直接放入有序数组的后面即可，然后接着往后取元素执行插入排序
• 如果当前元素小于最后一个元素，则执行交换操作，然后继续往前比较，直到无法进行交换操作或是到达有序数组的起始位置。
  

时间复杂度：

当前元素的选择次数为数组的长度为$N$N，在插入的过程中最好情况是每次只需要比较一次，所以最好时间复杂度为$O(N * 1) = O(N)$O(N∗1)=O(N)。最坏情况为每次都要和有序数组的所有元素交换，最坏时间复杂度为$O(N * N) =O(N^2)$O(N∗N)=O(N2)，平均时间复杂度为$O(N^2)$O(N2)。

空间复杂度：

由于排序过程直接在原数组上进行操作，并没有申请额外的空间，所以为$O(1)$O(1)

稳定性：

从排序的过程可以看出，如果存在两个相等元素，插入的过程不改变两个元素的相对位置。因此直接插入排序是一种稳定的排序算法

Java代码实现：

public class InsertionSort {

	public static void insertionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}

		// 当前元素的位置，从头到尾
		for (int i = 1; i < arr.length; i++) {
			// 然后比较当前元素和有序数组从后往前进行比较
			// 直到无法进行交换
			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
				swap(arr, j, j + 1);
			}
		}
	}

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

Python代码实现：

# 插入排序
def insert_sort(nums):
    # 起始将索引为0的位置当作有序序列，所以我们实际上只需要做 n - 1 次插入排序
    for i in range(0, len(nums) - 1):
        while i > 0:
            # 然后将无序序列的第一个元素插入到有序序列的合适位置
            if nums[i] < nums[i - 1]:
                nums[i], nums[i - 1] = nums[i - 1], nums[i]
                i -= 1
            # 当前元素正好放入有序序列最后的位置，则不执行交换操作，访问下一个元素
            else:
                break
        print('index: {} -- {}'.format(i, nums))
    
    return nums

if __name__ == "__main__":
    nums = [5, 2, 9, 7, 6, 12, 3, 4]

    # 插入排序
    print('insert sort result is: ', insert_sort(nums))