java实现八大排序算法

插入排序

概述

记录备用

一、直接插入排序

基本思想

往有序的数组中快速插入一个新的元素

步骤

  1. 从第一个元素开始,可以认为第一个元素已经排序
  2. 取出下一个元素a,在已经排序的数组从后往前扫描
  3. 如果a大于已排序的数组,则继续往下一个元素取;如果a小于已排序的数组,则和已排序的数组从后往前比较,找到合适的位置插入
  4. 重复2、3

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
public class insertionSort {
void insertionSort(int arr[]) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j > 0; j--) {
if (arr[j] >= arr[j - 1])
break;
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
}

二、希尔排序

基本思想

将待排序数组按照步长gap进行分组,然后将每组的元素利用直接插入排序的方法进行排序;每次再将gap折半减小,循环上述操作;当gap=1时,利用直接插入,完成排序。

步骤

  1. 选择一个增量序列,t1,t2,…,tk,tk=1;
  2. 按增量序列的个数,对序列进行k趟排序
  3. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class shellSort {
void shellSort(int arr[]) {
int gap = arr.length / 2;
//缩小gap,直到为1
for (; gap > 0; gap /= 2) {
//使用每个gap进行遍历
for (int j = 0; (j + gap) < arr.length; j++) {
for (int k = 0; (k + gap) < arr.length; k += gap) {
if (arr[k] > arr[k + gap]) {
int temp = arr[k + gap];
arr[k + gap] = arr[k];
arr[k] = temp;
}
}
}
if (gap == 1) {
break;
}
}

}
}

三、选择排序

基本思想

在未排序序列找到最大(小)元素,存放到未排序序列的起始位置

步骤

  1. 从待排序序列中,找到最小的元素
  2. 如果最小元素不会待排序元素的第一个元素,将其和第一个元素互换
  3. 从余下的n-1个元素中,找出最小的元素,重复1、2,直到排序结束

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class selectionSort {
void selectionSort(int arr[]){
for(int i=0;i<arr.length-1;i++){
int min=i;
for(int j=i+1;j<arr.length;j++){
if(arr[j]<arr[min]){
min=j;
}
}
if(min!=i){
int temp=arr[min];
arr[min]=arr[i];
arr[i]=temp;
}
}
}
}

四、堆排序

基本思想

堆是一种经过排序的完全二叉树,其中任意非叶子节点的值均不大于(或者不小于)其左子节点和右子节点的值,最大堆和最小堆是二叉堆的两种形式

以大顶堆为例,堆排序的过程就是将待排序的序列构造成一个堆,选出堆中最大的移走,再把剩余的元素调整成堆,找出最大的再移走,重复直至有序

步骤

  1. 建立堆
  2. 交换,从堆中提出最大数

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class heapSort {

public static void main(String[] args) {
int[] a={49,38,65,97,76,13,27,49,78,34,12,64};
int arrayLength=a.length;
//循环建堆
for(int i=0;i<arrayLength-1;i++){
//建堆
buildMaxHeap(a,arrayLength-1-i);
//交换堆顶和最后一个元素
swap(a,0,arrayLength-1-i);
System.out.println(Arrays.toString(a));
}
}
//对data数组从0到lastIndex建大顶堆
private static void buildMaxHeap(int[] data,int lastIndex){
//从lastIndex处节点(最后一个节点)的父节点开始
for(int i=(lastIndex-1)/2;i>=0;i--){
//k保存正在判断的节点
int k=i;
//如果当前k节点的子节点存在
while(k*2+1<=lastIndex){
//k节点的左子节点的索引
int biggerIndex=2*k+1;
//如果biggerIndex小于lastIndex,即biggerIndex+1代表的k节点的右子节点存在
if(biggerIndex<lastIndex){
//若果右子节点的值较大
if(data[biggerIndex]<data[biggerIndex+1]){
//biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
//如果k节点的值小于其较大的子节点的值
if(data[k]<data[biggerIndex]){
//交换他们
swap(data,k,biggerIndex);
//将biggerIndex赋予k,开始while循环的下一次循环,重新保证k节点的值大于其左右子节点的值
k=biggerIndex;
}else{
break;
}
}
}
}
public static void swap(int[] data,int i,int j){
int tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}

}

##五、冒泡排序

基本思想

重复的走访要访问的序列。一次比较两个元素,如果他们的顺序错误就交换过来,直到没有需要再交换,排序完成

步骤

  1. 比较相邻的元素,如果第一个比第二个大,就交换他们两个
  2. 对每一相邻元素做同样的工作,从开始的第一队对到结尾的最后一对,这步做完,最后的元素会是最大的元素
  3. 针对所有的元素重复以上的步骤,除了最后一个
  4. 持续1-3,直到没有任何元素需要比较

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class bubbleSort {
public static void bubbleSort(int[]arr){
int temp=0;
int size=arr.length;
for(int i=0;i<size-1;i++){
for(int j=0;j<size-1-i;i++){
if(arr[j]>arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
}

六、快速排序

基本思想

通过一趟快速排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分关键字小,则分别对这两部分进行排序,直至整个序列有序

步骤

  1. 从序列中挑出一个元素,称为基准
  2. 重新排序序列,所有比基准小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面,在这个分区结束后,该基准就处于数列的中间位置
  3. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class quickSort {
public static void quickSort(int[] arr, int low, int high){
if(arr.length <= 0) return;
if(low >= high) return;
int left = low;
int right = high;

int temp = arr[left]; //保存基准的值
while (left < right){
while(left < right && arr[right] >= temp){ //从后向前找到比基准小的元素,移动到低端
right--;
}
arr[left] = arr[right];
while(left < right && arr[left] <= temp){ //从前往后找到比基准大的元素,移动到高端
left++;
}
arr[right] = arr[left];
}
arr[left] = temp; //基准值填补
System.out.println("Sorting: " + Arrays.toString(arr));
quickSort(arr, low, left-1);
quickSort(arr, left+1, high);
}
}

七、归并排序

基本思想

归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

步骤

  1. 讲序列每相邻两个数字进行归并操作,形成floor(n/2)个序列,排序后每个序列包含两个元素
  2. 将上述序列再次合并,形成floor(n/4)个序列,每个序列包含四个元素
  3. 重复步骤2,直到所有元素排序完毕