八大排序算法是面试经常考到的,尤其是快排,希尔排序和归并也是经常会让写代码的题目,其实只要用一句话说明了他们的原理我们写起代码就没那么困难。
package Sorting;
import org.junit.jupiter.api.Test;
import java.util.Arrays;
public class Bubble {
public static void sort(int[] arr) {
for (int i=1;i<arr.length-1;++i) {
for(int j=0;j<arr.length-i;++j) {
if (arr[j] > arr[j + 1]) {
swap(arr,j);
}
}
}
}
private static void swap(int[] arr, int j) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
@Test
public void test() {
int[] arr = new int[]{2, 1, 4, 5, 3, 2};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
####分类:实际上插入排序是一个类别,它里面有很多具体的排序方式。直接插入排序,折半插入排序,希尔排序 ( 又称缩小增量排序 )。他们都是属于稳定排序。
package Sorting;
import org.junit.jupiter.api.Test;
import java.util.Arrays;
public class SimpleInsert {
public void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i - 1;
while (j > -1 && temp < arr[j]) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = temp;
}
}
@Test
public void test(){
int[] arr = new int[]{5, 3, 2, 6, 8, 1, 3, 0};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
package Sorting;
import org.junit.jupiter.api.Test;
import java.util.Arrays;
public class Shell {
public void sort(int[] arr) {
int step = arr.length / 2;
//这是循环每一个步长
while (step > 0) {
//这是循环每一个分组的第一个元素的下标
for (int i = 0; i <= step; i++) {
//这是一层简单插入排序
for (int ptr = i; ptr + step < arr.length; ptr += step) {
int temp = arr[ptr + step];
int j = ptr;
while (j >= 0 && arr[j] > temp) {
arr[j + step] = arr[j];
j -= step;
}
arr[j+step] = temp;
}
}
step /= 2;
}
}
@Test
public void test(){
int[] arr = new int[]{5, 3, 2, 6, 8, 1, 3, 0};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
package Sorting;
import org.junit.jupiter.api.Test;
public class SimpleSorting {
void sort(int[] arr) {
int min;
for (int i = 0; i < arr.length; i++) {
min = minIndex(arr, i);
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
private int minIndex(int[] arr, int start) {
int min = start;
for (int i = start; i < arr.length; i++) {
min = arr[i] < arr[min] ? i : min;
}
return min;
}
@Test
public void fun() {
int[] arr = new int[]{6, 2, 3, 4, 51, 32, 52, 33};
sort(arr);
for (int ele : arr) {
System.out.printf(ele + " ");
}
}
}
package Sorting;
import org.junit.jupiter.api.Test;
public class QuickSorting {
void sort(int[] arr, int start, int end) {
if (start >= end) {
return;
}
int center = getMid(arr, start, end);
sort(arr, start, center - 1);
sort(arr, center + 1, end);
}
void sort(int[] arr) {
sort(arr, 0, arr.length - 1);
}
int getMid(int[] arr, int start, int end) {
int temp = arr[start];
while (start < end) {
while (start < end && arr[end] >= temp) {
end--;
}
arr[start] = arr[end];
while (start < end && arr[start] <= temp) {
start++;
}
arr[end] = arr[start];
}
arr[start] = temp;
return start;
}
@Test
public void fun() {
int[] arr = new int[]{5, 3, 2, 6, 8, 1, 3, 0};
sort(arr);
for (int ele : arr) {
System.out.printf(ele + " ");
}
}
}
package Sorting;
import org.junit.jupiter.api.Test;
import java.util.Arrays;
public class Merge {
public static void sort(int []arr){
int []temp = new int[arr.length];//在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
sort(arr,left,mid,temp);//左边归并排序,使得左子序列有序
sort(arr,mid+1,right,temp);//右边归并排序,使得右子序列有序
merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
}
}
private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while(j<=right){//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}
@Test
public void fun() {
int[] arr = new int[]{5, 3, 2, 6, 8, 1, 3, 0, 9};
int[] temp = new int[arr.length];
sort(arr, 0, arr.length - 1, temp);
System.out.println(Arrays.toString(arr));
}
}
package Sorting;
import org.junit.jupiter.api.Test;
import java.util.Arrays;
public class HeapSort {
public static void sort(int []arr){
//1.构建大顶堆
for(int i=arr.length/2-1;i>=0;i--){
//从第一个非叶子结点从下至上,从右至左调整结构
swim(arr,i,arr.length);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for(int j=arr.length-1;j>0;j--){
swap(arr,0,j);//将堆顶元素与末尾元素进行交换
swim(arr,0,j);//重新对堆进行调整
}
}
/**
* 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上)
* @param arr
* @param i
* @param length
*/
public static void swim(int []arr,int i,int length){
int temp = arr[i];//先取出当前元素i
for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始,也就是2i+1处开始
if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点,k指向右子结点
k++;
}
if(arr[k] >temp){//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
/**
* 交换元素
* @param arr
* @param a
* @param b
*/
public static void swap(int []arr,int a ,int b){
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
@Test
public void fun() {
int[] arr = new int[]{5, 3, 2, 6, 8, 1, 3, 0};
sort(arr);
for (int ele : arr) {
System.out.printf(ele + " ");
}
}
}
(1)若n较小(如n≤50),可采用直接插入或直接选择排序。 当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。 (2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜; (3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短; 堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。 若要求排序稳定,则可选用归并排序。但前面介绍的从单个记录起进行两两归并的排序算法并不值得提倡,通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子序列,然后再两两归并之。因为直接插入排序是稳定 的,所以改进后的归并排序仍是稳定的。