[数据结构与算法] 06十大排序算法

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 06十大排序算法 -> 正文阅读

[数据结构与算法]06十大排序算法

算法的复杂度

时间复杂度

O(f(n))表示运行算法所需要的指令数，跟f(n)成正比，n表示数据规模。

空间复杂度

与n的使用有关，比如一个for循环且与n有关，则为O(n)，双重嵌套循环，且都与n有关，O(n^2)。

递归的深度是多少，空间复杂度就是多少

一个辅助一维数组为n，二维数组为n^2，常数为1。

算法的稳定性

通俗的来说，就是在a=b的情况下，a与b的位置有没有发生变化。若变化，则为不稳定，若不变，则稳定。

插入排序的原理以及实现

插入排序原理：

1.从待排序数组第二个数字开始选择

2.选定数字与该数组数字之前的数字比较（大或小自定）

3.若之前的数字比他大（或者小），数字后移移位

4.若遇到比他大（或者小）的数字，则跳出比较循环，将他放在此数字后面一位。

插入排序代码

package com.sdut.Demo07;

public class Demo02 {
	public static void main(String[] args) {
		int arr[] = new int[] { 25, 7, 18, 6, 1, 3, 9, 19 };
		
		InsertionSort(arr);
		
		for (int k : arr) {
			System.out.print(k + " ");
		}
		
	}

	public static void InsertionSort(int arr[]) {

		int i, j;

		for (i = 1; i < arr.length; i++) {
			int tmp = arr[i];
			for (j = i - 1; j >= 0; j--) {
				if (arr[j] > tmp) {
					arr[j + 1] = arr[j];
				}else {
					break;
				}
			}
			arr[j+1] = tmp;
		}
	}

}

希尔排序原理以及实现（缩小增量排序）

希尔排序原理

1.先确定第一个增量为数组长度/2

2.然后以此增量为间隔分组，并且在分组内进行插入排序

3.排序完成后，再次缩小增量 gap = gap / 2；

4.再次在分组内应用插入排序

5.直到分量为0时，跳出，输出最终结果

希尔排序代码：

package com.sdut.Demo07;

public class Demo03 {
	public static void main(String[] args) {

		int arr[] = new int[] { 25, 7, 18, 6, 1, 3, 9, 19 };

		HillSort(arr, arr.length);

		for (int k : arr) {
			System.out.print(k + " ");
		}

	}

	public static void HillSort(int arr[], int gap) {

		gap = gap / 2;

		while (gap >= 1) {
			int i, j;
			for (i = gap; i < arr.length; i++) {
				int tmp = arr[i];
				for (j = i - gap; j >= 0; j = j - gap) {
					if (arr[j] > tmp) {
						arr[j + gap] = arr[j];
					} else {
						break;
					}
				}
				arr[j + gap] = tmp;
			}
			gap = gap / 2;
		}
	}

}

选择排序原理以及实现

选择排序原理：

1.选择第一个为最小（或最大），与其他的数据相比较

2.若有数据比他小（或大），更新最小（最大）值，并记录下标值

3.若为最小，则与第一个位置互换，并且下一次的开始后移一位

4.若为最大，则与最后一位互换位置，并且下一次的比较的后边界值，前移一位

选择排序代码：

package com.sdut.Demo07;

public class Demo04 {
	public static void main(String[] args) {
		int arr[] = new int[] { 25, 7, 18, 6, 1, 3, 9, 19 };

		SelectSort(arr);
		for (int k : arr) {
			System.out.print(k + " ");
		}
	}
	/*最小的放在前面的情况
	public static void SelectSort(int arr[]) {
		for (int i = 0; i < arr.length - 1; i++) {
			int temp = arr[i];	//这里为什么是i？
			int minIndex = i;	//这里为什么也是i？
			for (int j = i + 1; j < arr.length; j++) {
				if (temp >= arr[j]) {
					temp = arr[j];
					minIndex = j;
				}
			}
			arr[minIndex] = arr[i];
			arr[i] = temp;
		}
	}
	*/
	//最大的放在后面
	public static void SelectSort(int arr[]) {
		for (int i = 0; i < arr.length - 1; i++) {
			int temp = arr[0];	//这里为什么是0？
			int maxIndex = 0;	//这里为什么也是0？
			for (int j = 1; j < arr.length - i; j++) {
				if (temp <= arr[j]) {
					temp = arr[j];
					maxIndex = j;
				}
			}
			arr[maxIndex] = arr[arr.length - i -1];
			arr[arr.length - i -1] = temp;
		}
	}
	
}

堆排序原理以及实现

在说明堆排序原理之前，需要明白什么是大大顶堆，小顶堆。

堆是一种二叉树的数据结构

**大顶堆：**即他的每一个父节点都大于等于他两个子节点。即 a[i] >= a[2 * i + 1]，与a[i] >= a[2 * i + 2]。

**小顶堆：**即他的每一个父节点都小于等于等于他两个子节点。即 a[i] <= a[2 * i + 1]，与a[i]<= a[2 * i + 2]。

堆排序原理：

升序排列（大顶堆）：

1.将数组构造为一个大顶堆

2.将最大的根节点与非叶子节点（即最小的节点）互换

3.将非叶子节点剔除在外，剩下的节点重新构造为一个大顶堆。

降序排列（小顶堆）：

1.将数组构造为一个小顶堆

2.将最小的根节点与非叶子节点（即最小的节点）互换

3.将非叶子节点剔除在外，剩下的节点重新构造为一个小顶堆。

堆排序代码（大顶堆）：

package com.sdut.Demo07;

public class Demo05 {
	public static void main(String[] args) {
		int arr[] = new int[] { 25, 7, 18, 6, 1, 3, 9, 19 };
		HeapSort(arr);
		
		for (int k : arr) {
			System.out.print(k + " ");
		}
	}

	public static void HeapSort(int arr[]) {
		// 第一步，构造大顶堆
		BuildBigTopPile(arr);
		// 第二部，重构造大顶堆
		int size = arr.length;
		while (size > 1) {
			// 最大值交换到非叶子节点（即最后一个节点）
			Exchange(arr, 0, size - 1);
			size--;// 长度减一
			// 重构造
			RebuildBigTopPile(arr, 0, size);
		}
	}

	// 构造大顶堆
	public static void BuildBigTopPile(int arr[]) {
		for (int i = 0; i < arr.length; i++) {
			// 记录当前节点
			int currentnode = i;
			// 推算父节点
			int fathernode = (currentnode - 1) / 2;
			while (arr[currentnode] > arr[fathernode]) {
				// 若当前节点的值大于父节点，则交换值
				Exchange(arr, currentnode, fathernode);
				// 交换值之后，将当前节点定义为他的父节点
				currentnode = fathernode;
				// 交换完成，获取父节点的父节点，循环判断大小
				fathernode = (currentnode - 1) / 2;
			}
		}
	}

	public static void RebuildBigTopPile(int arr[], int index, int size) {
		int left = 2 * index + 1;
		int right = 2 * index + 2;
		// 保证左节点在数组范围内
		while (left < size) {
			int topnode;// 存储最大的孩子节点

			if (arr[left] < arr[right] && right < size) {
				topnode = right;
			} else {
				topnode = left;
			}

			// 判断最大子节点与父节点的值
			if (arr[index] > arr[topnode]) {
				topnode = index;
			}

			// 如果父节点大，则不需要或者已经构造完毕，跳出循环
			if (topnode == index) {
				break;
			}
			// 如果父节点小，则交换两个节点的值
			Exchange(arr, topnode, index);
			// 交换完成后，索引指向被交换的孩子节点，继续下一轮判断（因为他被交换过）
			index = topnode;
			// 重新计算他的孩子节点
			left = 2 * index + 1;
			right = 2 * index + 2;
		}

	}

	public static void Exchange(int arr[], int currentnode, int fathernode) {
		int taget = arr[currentnode];
		arr[currentnode] = arr[fathernode];
		arr[fathernode] = taget;
	}
}

堆排序代码（小顶堆）：（即，将一些大于号，换为小于号）

package com.sdut.Demo07;

public class Demo06 {
	public static void main(String[] args) {
		int arr[] = new int[] { 25, 7, 18, 6, 1, 3, 9, 19 };
		HeapSort(arr);
		
		for (int k : arr) {
			System.out.print(k + " ");
		}
	}

	public static void HeapSort(int arr[]) {
		// 第一步，构造小顶堆
		BuildBigTopPile(arr);
		// 第二部，重构造小顶堆
		int size = arr.length;
		while (size > 1) {
			// 最小值交换到非叶子节点（即最后一个节点）
			Exchange(arr, 0, size - 1);
			size--;// 长度减一
			// 重构造
			RebuildBigTopPile(arr, 0, size);
		}
	}

	// 构造小顶堆
	public static void BuildBigTopPile(int arr[]) {
		for (int i = 0; i < arr.length; i++) {
			// 记录当前节点
			int currentnode = i;
			// 推算父节点
			int fathernode = (currentnode - 1) / 2;
			while (arr[currentnode] < arr[fathernode]) {
				// 若当前节点的值小于父节点，则交换值
				Exchange(arr, currentnode, fathernode);
				// 交换值之后，将当前节点定义为他的父节点
				currentnode = fathernode;
				// 交换完成，获取父节点的父节点，循环判断大小
				fathernode = (currentnode - 1) / 2;
			}
		}
	}

	public static void RebuildBigTopPile(int arr[], int index, int size) {
		int left = 2 * index + 1;
		int right = 2 * index + 2;
		// 保证左节点在数组范围内
		while (left < size) {
			int topnode;// 存储最小的孩子节点

			if (arr[left] > arr[right] && right < size) {
				topnode = right;
			} else {
				topnode = left;
			}

			// 判断最小子节点与父节点的值
			if (arr[index] < arr[topnode]) {
				topnode = index;
			}

			// 如果父节点小，则不需要或者已经构造完毕，跳出循环
			if (topnode == index) {
				break;
			}
			// 如果父节点大，则交换两个节点的值
			Exchange(arr, topnode, index);
			// 交换完成后，索引指向被交换的孩子节点，继续下一轮判断（因为他被交换过）
			index = topnode;
			// 重新计算他的孩子节点
			left = 2 * index + 1;
			right = 2 * index + 2;
		}

	}

	public static void Exchange(int arr[], int currentnode, int fathernode) {
		int taget = arr[currentnode];
		arr[currentnode] = arr[fathernode];
		arr[fathernode] = taget;
	}
}

冒泡排序的原理以及实现

冒泡排序原理：

1.从下标为零的元素开始，相邻的两个元素进行比较，并把较大的数放在后面

2.每一次冒泡都会把最大的数放在最后面，所以需要进行数组长度-1次冒泡

3.最大的放在后面，所以第二次冒泡要找出次大的，还要保证时空复杂度，所以，每一次比较的元素个数都是元素总数-次数-1-1

冒泡排序代码：

package com.sdut.Demo07;

public class Demo01 {
	public static void main(String[] args) {
		int arr[] = new int[] { 25, 7, 18, 6, 1, 3, 9, 19 };
		
		BubbleSort(arr);
		
		for (int k : arr) {
			System.out.print(k + " ");
		}
		
	}

	public static void BubbleSort(int arr[]) {

		int taget;

		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = 0; j < arr.length - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					taget = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = taget;
				}
			}
		}
	}
}

快速排序的原理以及实现

快速排序原理：

1.在数组里选择一个数，一般为第一个数据

2.将比之大的放在该书的右边，比之小的放在该数据的左边

3.然后再对左右两边进行如上操作，知道指向每一组新数组的左右指针指向同一个数据，即数组内只剩一个数据

快速排序代码：

package com.sdut.Demo07;

public class Demo07 {
	public static void main(String[] args) {
		int arr[] = new int[] { 18, 7, 25, 6, 1, 3, 9, 19 };

		Sort(arr, 0, arr.length-1);
		
		for (int k : arr) {
			System.out.print(k + " ");
		}
		
	}

	public static void Sort(int arr[], int star, int end) {
		if (star < end) {
			int index = QuickSort(arr, star, end);

			QuickSort(arr, star, index - 1);
			QuickSort(arr, index + 1, end);
		}
	}

	public static int QuickSort(int arr[], int star, int end) {
		int taget = arr[star];
		int i = star;
		int j = end;
		while (i < j) {
			while (i < j && arr[j] >= taget) {
				j--;
			}
			if (i < j) {
				arr[i] = arr[j];
				i++;
			}

			while (i < j && arr[i] < taget) {
				i++;
			}
			if (i < j) {
				arr[j] = arr[i];
				j--;
			}
		}

		arr[i] = taget;
		return i;
	}

}

另外一种递归代码是写在实现方法里面的

package com.sdut.Demo07;

public class Demo08 {
	public static void main(String[] args) {
		int arr[] = new int[] { 18, 7, 25, 6, 1, 3, 9, 19 };

		QuickSort(arr, 0, arr.length - 1);

		for (int k : arr) {
			System.out.print(k + " ");
		}

	}

	public static void QuickSort(int arr[], int star, int end) {
		if (star < end) {
			int taget = arr[star];
			int i = star;
			int j = end;
			while (i < j) {
				while (i < j && arr[j] >= taget) {
					j--;
				}
				if (i < j) {
					arr[i] = arr[j];
					i++;
				}

				while (i < j && arr[i] < taget) {
					i++;
				}
				if (i < j) {
					arr[j] = arr[i];
					j--;
				}
			}

			arr[i] = taget;
			QuickSort(arr, star, i - 1);
			QuickSort(arr, i + 1, end);
		}
	}

}

归并排序的原理以及实现

归并排序原理：

将字符串分割，一直分割到最小，即一个数据一组
将两组分割好的数据放在一块比较
创建一个临时的，大小为两组数据之和的数组
分别对两组数据进行比较
三个指针，一个指向新数组，另外两个分别指向分割的数组
小的先入
一直递归

归并排序代码：

package com.sdut.Demo07;

public class Demo09 {
	public static void main(String[] args) {
		int arr[] = new int[] { 25, 7, 18, 6, 1, 3, 9, 19 };

		sort(arr, 0, arr.length - 1);

		for (int k : arr) {
			System.out.print(k + " ");
		}
	}

	public static void sort(int arr[], int star, int end) {
		if (star < end) {
			int mid = (star + end) / 2;

			sort(arr, star, mid);
			sort(arr, mid + 1, end);

			mergeSort(arr, star, end, mid);
		}
	}

	public static void mergeSort(int arr[], int star, int end, int mid) {
		int arr01[] = new int[end - star + 1];

		int i = star;
		int j = mid + 1;
		int k = 0;
		while (i <= mid && j <= end) {
			if (arr[i] < arr[j]) {
				arr01[k++] = arr[i++];
			} else {
				arr01[k++] = arr[j++];
			}
		}
		while (i <= mid) {
			arr01[k++] = arr[i++];
		}
		while (j <= end) {
			arr01[k++] = arr[j++];
		}

		for (int k1 = 0; k1 < arr01.length; k1++) {
			arr[k1 + star] = arr01[k1];
		}
	}
}

计数排序的原理以及实现

计数排序的原理：

获得数组的最大最小值
创建一个长度为max - min +1的数组来存储数据
利用新创建的数组来计算数据出现的次数以及位置
最后还原数据，填充到原数组

计数排序代码：

package com.sdut.Demo07;

import java.util.HashMap;
import java.util.Map;

public class Demo11 {
	public static void main(String[] args) {
		int arr[] = new int[] { 25, 7, 18, 6, 1, 3, 9, 19 };
		
		countSort(arr);
		
		for (int k : arr) {
			System.out.print(k + " ");
		}
	}

	public static Map<String, Integer> data(int arr[]) {
		Map<String, Integer> map = new HashMap<String, Integer>();

		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;

		for (int i = 0; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
			if (arr[i] < min) {
				min = arr[i];
			}
		}

		map.put("max", max);
		map.put("min", min);

		return map;

	}

	public static void countSort(int arr[]) {
		Map<String, Integer> map = data(arr);
		int max = map.get("max");
		int min = map.get("min");

		int mid[] = new int[max - min + 1];

		for (int i = 0; i < arr.length; i++) {
			mid[arr[i] - min]++;
		}

		int index = 0;
		for (int i = 0; i < mid.length; i++) {
			while (mid[i] > 0) {
				arr[index++] = min + i;
				mid[i]--;
			}
		}
	}

}

计数排序的另外一种方法：（这种方法具有缺陷性，数组内不能出现相同的数据）

package com.sdut.Demo07;

import java.util.HashMap;
import java.util.Map;

public class Demo12 {
	public static void main(String[] args) {
		int arr[] = new int[] { 25, 7, 18, 6, 1, 3, 9, 19 };

		countSort(arr);
	}

	public static Map<String, Integer> data(int arr[]) {
		Map<String, Integer> map = new HashMap<String, Integer>();

		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;

		for (int i = 0; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
			if (arr[i] < min) {
				min = arr[i];
			}
		}

		map.put("max", max);
		map.put("min", min);

		return map;

	}

	public static void countSort(int arr[]) {
		Map<String, Integer> map = data(arr);
		int max = map.get("max");
		int min = map.get("min");

		int mid[] = new int[max - min + 1];
		int end[] = new int[arr.length];

		for (int i = 0; i < arr.length; i++) {
			mid[arr[i] - min]++;
		}
		// 计算偏移量
		for (int i = 1; i < mid.length; i++) {
			mid[i] = mid[i] + mid[i - 1];
		}
		for (int i = 0; i < arr.length; i++) {
			end[mid[arr[i] - min] - 1] = arr[i];
		}
		
		for (int k : end) {
			System.out.print(k + " ");
		}
	}

}

桶排序的原理以及实现

桶排序的原理：

将一组数据，均匀的分布在几个区间
然后每一个区间使用排序算法（任意一种）
最后把每个区间的数据组合起来

桶排序代码：

package com.sdut.Demo07;

import java.util.ArrayList;
import java.util.List;
public class Demo14 {
	public static void main(String[] args) {
		int a[]= {1,8,7,44,42,46,38,34,33,17,15,16,27,28,24};
		List[] buckets=new ArrayList[5];
		for(int i=0;i<buckets.length;i++)//初始化
		{
			buckets[i]=new ArrayList<Integer>();
		}
		for(int i=0;i<a.length;i++)//将待排序序列放入对应桶中
		{
			int index=a[i]/10;//对应的桶号
			buckets[index].add(a[i]);
		}
		for(int i=0;i<buckets.length;i++)//每个桶内进行排序(使用系统自带快排)
		{
			buckets[i].sort(null);
			for(int j=0;j<buckets[i].size();j++)//顺便打印输出
			{
				System.out.print(buckets[i].get(j)+" ");
			}
		}	
	}
}

基数排序的原理以及实现

基数排序原理：

获取数据的最高位数
定义一个长度为10的二维数组
第一次取余，然后放入二维数组中
取出
第二次取余，即取的十位数，放入数组中
去处
依次执行到取到最大位
排序完毕

基数排序代码：

package com.sdut.Demo07;

import java.util.Arrays;


public class Demo15 {

	public static void main(String[] args) {
		int[] arr = new int[] { 23, 6, 9, 287, 56, 1, 789, 34, 65, 653 };
		radixSort(arr);
		System.out.println(Arrays.toString(arr));
	}

	public static void radixSort(int[] arr) {

		// 存数组中最大的数字,为了知道循环几次
		int max = Integer.MIN_VALUE;// (整数中的最小数)
		// 遍历数组，找出最大值
		for (int i = 0; i < arr.length; i++) {
			if (max < arr[i]) {
				max = arr[i];
			}
		}

		// 计算最大数是几位数,,此方法计较绝妙
		int maxLength = (max + "").length();
		// 用于临时存储数据的数组
		int[][] temp = new int[10][arr.length];
		// 用于存储桶内的元素位置
		int[] counts = new int[arr.length];

		// 第一轮个位数较易得到余数，第二轮就得先除以十再去取余，之后百位除以一百
		// 可以看出，还有一个变量随循环次数变化，为了取余

		// 循环的次数
		for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
			// 每一轮取余
			for (int j = 0; j < arr.length; j++) {
				// 计算余数
				int ys = (arr[j] / n) % 10;
				// 把数据放在指定数组中，有两个信息，放在第几个桶+数据应该放在第几位
				temp[ys][counts[ys]] = arr[j];
				// 记录数量
				counts[ys]++;
			}

			// 记录取的数字应该放到位置
			int index = 0;
			// 每一轮循环之后把数字取出来
			for (int k = 0; k < counts.length; k++) {
				// 记录数量的数组中当前余数记录不为零
				if (counts[k] != 0) {
					for (int l = 0; l < counts[k]; l++) {
						// 取出元素
						arr[index] = temp[k][l];
						index++;
					}
					// 取出后把数量置为零
					counts[k] = 0;
				}
			}

		}
	}

}