[数据结构与算法]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);
		}
	}

}

归并排序的原理以及实现

归并排序原理：

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

归并排序代码：

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];
		}
	}
}

计数排序的原理以及实现

计数排序的原理：

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

计数排序代码：

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 + " ");
		}
	}

}

桶排序的原理以及实现

桶排序的原理：

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

桶排序代码：

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)+" ");
			}
		}	
	}
}

基数排序的原理以及实现

基数排序原理：

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

基数排序代码：

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;
				}
			}

		}
	}

}