Java数据结构算法（五）排序
2018-08-12 本文已影响0人
Active_Loser
算法这点粗略整理一下，后面完善
一、插入排序
1、 直接插入排序
直接插入排序(Straight Insertion Sort)的基本思想是：每次将一个待排序的元素与已排序的元素进行逐一比较，直到找到合适的位置按大小插入。
举一个简单的例子，我们玩扑克牌时，我们往往会从第一张牌开始依次整理牌的顺序，而将后面的牌插入在其他牌中的过程就是插入排序。
算法实现
package sort;
/**
* Author: Active_Loser
* Date: 2018/8/5 22:18
* Content: 直接插入排序，正序排列
*/
public class InsertSort {
public static void main(String[] args) {
int[] arr = {14, 20, 9, 12, 10};
//从第二个数字开始遍历
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j;
for (j = i - 1; j >= 0; j--) {
//比较插入的数于前面的数，若需要排序的数组大于前面的数，则将去后移一位
if (temp < arr[j]) {
arr[j + 1] = arr[j];
} else {
break;
}
}
//将数字插入
arr[j + 1] = temp;
}
for (int i = 0; i < arr.length; i++) {
System.out.println("" + arr[i]);
}
}
}
2、二分法插入排序
分法插入排序是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left<right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。
算法实现
package sort;
/**
* Author: Active_Loser
* Date: 2018/8/5 23:19
* Content: 二分法插入排序,正序排序
*/
public class BinaryInsertSort {
public static void main(String[] args) {
int[] arr = {14, 20, 9, 12, 10};
for (int i = 0; i < arr.length; i++) {
int temp = arr[i];
int left = 0;
int right = i;
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (temp > arr[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
//需要插入的数之前大于插入数的其他数需要向后移动一位
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
//判断是否需要插入
if (left != i) {
arr[left] = temp;
}
}
for (int i = 0; i < arr.length; i++) {
System.out.println("" + arr[i]);
}
}
}
3、希尔排序
对于大规模乱序数组插入很慢，因为他们只能交换相邻的元素，因此移动很慢。希尔排序是为了加快速度简单的改进了插入排序，交换不相邻的元素以对数组的局部进行更新，并最终用插入排序将局部有序的进行数组排序。
希尔排序是非稳定排序算法，它把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
算法实现
package sort;
/**
* Author: Active_Loser
* Date: 2018/8/6 0:05
* Content:希尔排序，正序
*/
public class ShellSort {
public static void main(String[] args) {
int[] arr = {1, 9, 20, 89, 66, 31, 15, 17, 20, 40, 60};
int d = arr.length / 3;//默认增量为6
while (true) {
for (int i = 0; i < d; i++) {
for (int j = i; j + d < arr.length; j += d) {
//i=0--->1 89
//对值进行比较
int tmp;
if (arr[j] > arr[j + d]) {
tmp = arr[j];
arr[j] = arr[j + d];
arr[j + d] = tmp;
}
}
}
//对增量的值进行更新
if (d == 1) {
break;
}
d--;
}
for (int i = 0; i < arr.length; i++) {
System.out.println("" + arr[i]);
}
}
}
二、选择排序
1、简单选择排序
每一趟从待排序的数据元素中选出最小（最大）的元素，顺序放在待排序的数列最前，直到全部待排序的数据元素全部排完。
算法实现
package sort;
/**
* Author: Active_Loser
* Date: 2018/8/6 22:29
* Content:简单选择排序
*/
public class selectSort {
public static void main(String[] args) {
int[] arr = {14, 20, 9, 12, 10};
for (int i = 0; i < arr.length; i++) {
//temp用于记录交换过程中的最小值
int temp = arr[i];
//flag用于记录下标
int flag = -1;
for (int j = i; j < arr.length; j++) {
if (temp > arr[j]) {
flag = j;
temp = arr[j];
}
}
if (flag != -1) {
arr[flag] = arr[i];
arr[i] = temp;
}
}
for (int i = 0; i < arr.length; i++) {
System.out.println("" + arr[i]);
}
}
}
2、堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。
堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。小根堆的要求是每个节点的值都小于其父节点的值。大根堆的要求是每个节点的值都不大于其父节点的值。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
我们从下图可以发下一个规律：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
package sort;
/**
* Author: Active_Loser
* Date: 2018/8/6 22:52
* Content:堆排序，升序
*/
public class HeapSort {
public static void main(String[] args) {
int[] arr = {1, 9, 20, 89, 66, 31, 15, 17, 20, 40, 60};
heapSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println("" + arr[i]);
}
}
public static void heapSort(int[] arr) {
if (arr == null) {
return;
}
//构建大堆
buildHeapMax(arr);
for (int i = arr.length - 1; i >= 0; i--) {
//交换第一个值（最大值)和沉淀前的值交换，这样就将大的值沉淀下去
//每遍历依次就沉淀一个大元素
exchangeElements(arr, 0, i);
//每一次大堆构造，从零开始构造，沉淀的值无需构造
maxHeep(arr, i-1, 0);
}
}
/**
* 构建大堆，从后往前构造，避免对后面的元素造成印象
* @param arr
*/
private static void buildHeapMax(int[] arr) {
//根据二叉树下标的特点，只用遍历一半即可获取全部下标，即可构建大堆
int half = (arr.length - 1) / 2;
//从后面的元素往前面的排
for (int i = half; i >= 0; i--) {
maxHeep(arr, arr.length, i);
}
}
/**
* 对大堆进行排序
* @param arr 数组
* @param length 需要排序数组长度
* @param i 从下标为多少构造
*/
private static void maxHeep(int[] arr, int length, int i) {
int left = 2 * i + 1;//二叉树中，左子树的下标是根节点的2倍+1
int right = 2 * i + 2;//二叉树中，左子树的下标是根节点的2倍+2
int largst = i;
//左子树的值大于根节点的值
if (left < length && arr[left] > arr[largst]) {
largst = left;
}
//左子树的值大于根节点的值
if (left < length && arr[right] > arr[largst]) {
largst = right;
}
if (i != largst) {
exchangeElements(arr, i, largst);
//当largst下标所代表的值交换后，需要对其重新判断
maxHeep(arr, length, largst);
}
}
/**
* 交换2个值
*/
private static void exchangeElements(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
三、交换排序
1、冒泡排序
它重复地走访过要排序的元素列，一次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
2、快速排序
package sort;
/**
* Author: Active_Loser
* Date: 2018/8/9 21:06
* Content: 快速排序
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = {14, 9, 10, 23, 77, 78, 1, 20, 79, 5, 31};
quickSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println("args = [" + arr[i] + "]");
}
}
public static void quickSort(int[] arr) {
if (arr.length == 0) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int middle = getMiddle(arr, low, high);
quickSort(arr, 0, middle - 1);//操作中心点左边的数据
quickSort(arr, middle + 1, high);
}
}
/**
* 获取中心点
*/
public static int getMiddle(int[] arr, int low, int high) {
int povit = arr[low];//默认为基准
while (low < high) {
while (low < high && arr[high] >= povit) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= povit) {
low++;
}
arr[high] = arr[low];
}
arr[low] = povit;//找到的中心节点的位置就是low所处的位置，将值改为基准的值
return low;
}
}
四、归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
package sort;
/**
* Author: Active_Loser
* Date: 2018/8/9 21:52
* Content:归并排序
*/
public class MergeSort {
public static void main(String[] args) {
int[]arr= {12,27,23,2,62,98,13,15,2};
mergeSort(arr, 0, arr.length-1);
for(int i=0;i<arr.length;i++) {
System.out.print(arr[i]+"、");
}
}
public static void mergeSort(int arr[],int left,int right) {
if(left<right) {
int mid=(left+right)/2;
mergeSort(arr, left, mid);
mergeSort(arr, mid+1, right);
merge(arr,left,mid,right);
}
}
public static void merge(int arr[],int left,int mid,int right) {
int temArr[]=new int[arr.length];
int rs=mid+1;//右边数组开始的下标
int point=left;//temArr数组下标
int temp=left;//用于赋值数组的下标
while(left<=mid&&rs<=right) {
if(arr[left]<=arr[rs]) {
temArr[point++]=arr[left++];
}else {
temArr[point++]=arr[rs++];
}
}
while(left<=mid) {
temArr[point++]=arr[left++];
}
while(rs<=right) {
temArr[point++]=arr[rs++];
}
while(temp<=right) {
arr[temp]=temArr[temp++];
}
}
}
五、基数排序
基数排序属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用.
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
package sort;
public class RadixSort {
public static void sort(int[] number, int d) //d表示最大的数有多少位
{
int k = 0;
int n = 1;
int m = 1; //控制键值排序依据在哪一位
int[][]temp = new int[10][number.length]; //数组的第一维表示可能的余数0-9
int[]order = new int[10]; //数组orderp[i]用来表示该位是i的数的个数
while(m <= d)
{
for(int i = 0; i < number.length; i++)
{
int lsd = ((number[i] / n) % 10);
temp[lsd][order[lsd]] = number[i];
order[lsd]++;
}
for(int i = 0; i < 10; i++)
{
if(order[i] != 0)
for(int j = 0; j < order[i]; j++)
{
number[k] = temp[i][j];
k++;
}
order[i] = 0;
}
n *= 10;
k = 0;
m++;
}
}
public static void main(String[] args)
{
int[]data ={73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};
RadixSort.sort(data, 3);
for(int i = 0; i < data.length; i++)
{
System.out.print(data[i] + "");
}
}
}
