並べ替えアルゴリズムには様々なアルゴリズムと最適化(発泡体の並べ替え、直接並べ替え、ヒルの並べ替え、高速の並べ替え、積み上げ、並べ替え、基数の並べ替え、カウントアップ、バケツの並べ替え)が含まれています.
18373 ワード
最近は面接のため、アルゴリズムをちゃんと勉強していません.泡が出てきて、直接に並べ替えて、ヒルの並べ替え、快速的な並べ替え、積み上げ、並べ替え、基数順、数え順、桶の並べ替えを書いてきました.
一、泡の並べ替え
一、泡の並べ替え
/**
* Created by april on 2018/8/3.
* O（n ）
*/
public class Bubble_sort
{
public static void main(String[] args){
int [] arr = {1,1,2,0,9,3,12,7,8,3,4,65,22};
BubbleSort_3(arr,arr.length);
for(int i: arr){
System.out.print(i+",");
}
}
public static void BubbleSort_1(int[] a ,int n){
for(int i=0; ia[j]){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
/* 1：
1、 n ， ，
2、 flag,
* */
public static void BubbleSort_2(int[] a, int n){
boolean flag = true;
int k = n;
while(flag){
flag = false;
for (int j=0;ja[j+1]){//
int temp;
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
flag = true;
}
}
k--;//
}
}
/* 2：
1000 ， 100 ， 900 100
1、 900 ， ， 900
2、 BubbleSort_2
* */
public static void BubbleSort_3(int[] a, int n){
int k;
int flag = n;
while(flag > 0 ){//
k = flag;// k
flag = 0;
for(int j = 0; j< k-1; j++){
if(a[j]>a[j+1]){
int temp;
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
flag = j+1;//
}
}
}
}
} /**
* Created by april on 2018/8/3.
*
* O（n ）
*/
public class Straight_insertion
{
public static void main(String[] args){
int[] arr = {1,1,2,0,9,3,12, 7, 8, 3, 4, 65, 22};
Straight_insertion.insertSort_3(arr,arr.length);
for(int i : arr){
System.out.print(i+",");
}
}
/*
a[i] a[0...i-1] a[0...i]
i++ i=n-1，
* */
public static void insertSort_1(int[] a, int n){
int i,j;
for(i=1; ia[i]) break;// a[j] a[i] ， a[i] , a[j]
}
// a[i] a[j]
int temp = a[i];// a[i]
for(int k = i-1; k>=j;k--){//a[j] a[i-1]
a[k+1] = a[k];
}
a[j] = temp;// a[i] a[j]
}
}
/*
1：
，a[i] a[i-1] ， a[i-1]a[i]を しながら し、j=i-1、a[j]を ろに しながら きに すると、a[i]より きいのがありますか？
*/
public static void insertSort_2(int[]a，int n){
int i，j
for（i=1；ia[i-1]）{
int temp=a[i]// するデータを する
for（j=i-1；j>=0&a[j]temp;j--）{
a[j＋1]=a[j]//i-1を ろに する
)
//データの
a[j＋1]=temp
)
)
)
//* 2：
1、a[i]は のa[i-1]と して、 のより さいなら、ずっと のと します。
*/
public static void insertSort_3(int[]a，int n){
int i，j
for（i=1；i=0&a[j]>a[j＋1];j--）{
int temp=a[j]
a[j]=a[j＋1]
a[j＋1]=temp
)
)
)
) /**
* Created by april on 2018/8/8.
* ： ， ， O（n ）
* ：
* ， ：gap = length/2,gap = gap/2
* ： gap = length/2 ，
* gap = gap/2
* gap=1,
*
*/
public class Shell_sort
{
public static void main(String[] args){
int[] arr = {49,38,65,97,76,13,27,49,55,04};
System.out.println(Arrays.toString(arr));
move_sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void move_sort(int[] arr){
for(int gap = arr.length/2;gap>0;gap/=2){// gap， gap 1
for(int i = gap;i=0&&temp /**
* Created by april on 2018/8/3.
* ， ， O(n ), O（nlogn）,
*/
public class Quick_sort
{
public static void main(String[] args){
// int[] arr = {49,38,65,97,76,13,27,49};
// Quick_sort.Quick_1(arr,0,arr.length-1);
// for(int i:arr){
// System.out.print(i+",");
// }
// 2 2 5 3 8 4 2 1
ListNode head = new ListNode(2);
ListNode l1 = new ListNode(2);
ListNode l2 = new ListNode(5);
ListNode l3 = new ListNode(3);
ListNode l4 = new ListNode(8);
ListNode l5 = new ListNode(4);
ListNode l6 = new ListNode(2);
ListNode l7 = new ListNode(1);
//
head.next = l1;
l1.next = l2;
l2.next = l3;
l3.next = l4;
l4.next = l5;
l5.next = l6;
l6.next = l7;
l7.next = null;
ListNode p = head;
while (p.next != null){
System.out.print(p.val+" ");
p = p.next;
}
// ，
System.out.println(p.val);
ListNode begin = head, end = p;
Quick_ListNode(begin,end);// ， ，
p = head;
while (p!=null){
System.out.print(p.val+" ");
p = p.next;
}
}
/*
（1） key， a[0], ， key ， key ， a[low] a[high]， a[low] key
（2） ， Key ， key ， a[low] a[high]， a[low] a[high]， a[high]= a[low]
(3)
* */
public static int One_Quick(int[] a,int low, int high){
int key=a[low];
while(lowkey)//while low=high) return;
//
int index = One_Quick(a,low,high);
//
Quick_1(a,low,index-1);
//
Quick_1(a,index+1,high);
}
/* , key ， key
1、 ，first second,first ，second first.next ，key first;
2、 second ， second>key, first->first.next，swap(first,second) 3、 second->second.next， second
4、 first ，
5、
* */
public static void Quick_ListNode(ListNode begin,ListNode end){
if(begin == null || end == null || begin==end){
return;
}
ListNode first = begin;
ListNode key = first;
ListNode second = begin.next;
while(second != end.next && second != null){// second
if(second.val>key.val){
first=first.next;
swap(first,second);
}
second = second.next;
}
if(begin != first)
{
swap(begin,first);
}
Quick_ListNode(begin,first);
Quick_ListNode(first.next,end);
}
public static void swap(ListNode first,ListNode second){
int temp;
temp = first.val;
first.val = second.val;
second.val = temp;
}
} /**
* Created by april on 2018/8/7.
*
* ：
* ，
* ，
* n-1 ， n
*
*/
public class Heap_sort
{
public static void main(String[] args){
int[] arr = {70,60,12,40,30,8,10};
heap_sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heap_sort(int[] arr){
//
for(int i = arr.length/2-1; i>=0; i--){
adjust_heap(arr,i,arr.length);// ，
}
// ，
for(int j = arr.length-1; j>0;j--){
swap(arr,0,j);
adjust_heap(arr,0,j);//
}
}
// ,
public static void adjust_heap(int[] arr, int i, int length){
int temp = arr[i];
for(int k = i*2+1;ktemp){// ， （ ），
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;// temp
}
//
public static void swap(int[] arr,int a,int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
} /**
* Created by april on 2018/8/4.
* O(nlogn)
*
* ，
*/
public class Merge_sort
{
public static void main(String[] args){
//
// int[] arr = {49,38,65,97,76,13,27};
// Merge_sort.sort(arr);
// System.out.println(Arrays.toString(arr));
//
ListNode head = new ListNode(0);
ListNode l1 = new ListNode(2);
ListNode l2 = new ListNode(5);
ListNode l3 = new ListNode(3);
ListNode l4 = new ListNode(8);
ListNode l5 = new ListNode(4);
ListNode l6 = new ListNode(2);
ListNode l7 = new ListNode(1);
//
head.next = l1;
l1.next = l2;
l2.next = l3;
l3.next = l4;
l4.next = l5;
l5.next = l6;
l6.next = l7;
l7.next = null;
ListNode p = head;
while (p.next != null){
System.out.print(p.val+" ");
p = p.next;
}
// ，
System.out.print(p.val);
System.out.println();
new Merge_sort().merge_sort(head);
p = head;
while(p!=null){
System.out.print(p.val+" ");
p = p.next;
}
}
/* 、 ， ， ， ， */
// ， ，
public static void sort(int[] arr){
int[] temp = new int[arr.length];
mergeSort(arr,0,arr.length-1,temp);
}
// 、 ，
//
public static void mergeSort(int[] a, int first, int last, int[] temp){
if(first < last){
int mid = (first+last)/2;
mergeSort(a,first,mid,temp);//
mergeSort(a,mid+1,last,temp);//
mergeArray(a,first,mid,last,temp);//
}
}
// ，a[first,mid] a[mid+1,end]
private static void mergeArray(int[] a, int first, int mid, int last, int[] temp){
int i = first, j = mid+1;//
//int m = mid, n = last;//
int k=0;//temp
while(i <= mid && j <= last){
if(a[i] <= a[j]){
temp[k++] = a[i++];
}else{
temp[k++] = a[j++];
}
}
while(i<=mid){
temp[k++] = a[i++];
}
while (j<=last){
temp[k++] = a[j++];
}
k = 0;
while(first<=last){
a[k++] = temp[k++];// temp ，
}
}
/* 、
* （1） ：
* （2） ， ，p1 p2 ，p1 ，p2 ， p2 ，p1
* */
//
public ListNode merge_split(ListNode head){
if(head == null) return head;
ListNode p1 = head;
ListNode p2 = head;
while(p2.next != null && p2.next.next != null){// p2 next ，p2 ， p2
p1 = p1.next;//p1
p2 = p2.next.next;//p2
}
return p1;// p1
}
//
public ListNode merge(ListNode first,ListNode second){
//
ListNode dummyHead = new ListNode(0);
ListNode curr = dummyHead;
while(first != null && second != null){//
if(first.val <= second.val){
curr.next = first;//
first = first.next;
}else{
curr.next = second;
second = second.next;
}
curr = curr.next;
}
curr.next = (first == null) ? second : first;
return dummyHead.next;
}
//
public ListNode merge_sort(ListNode head){
//[i...middle] [middle+1...n]
if(head == null || head.next == null) return head;
ListNode middle = merge_split(head);
ListNode shalf = middle.next;//
middle.next = null;//
return merge(merge_sort(head),merge_sort(shalf));
}
}/**
* Created by april on 2018/8/8.
*
*
* ：
* LSD： ， ， 。 1，2，3，4，5，6，7，8，9，10，11 ”b, c, d, e, f, g, h, i, j, ba” 。
* MSD: ， 、 。 ：1, 10, 2, 3, 4, 5, 6, 7, 8, 9 “b, ba, c, d, e, f, g, h, i, j”。
*
* ： 0~9 ， ， ， ，
： {73，22,93,43,55,14,28,65,39,81}
bucket[10][arr.length] ， 0~9 ， （ ）
0 1 2 3 4 5 6 7 8 9
1、
0 1 2 3 4 5 6 7 8 9
81 22 73 14 55 28 39
93 65
43
{81,22,73,93,43,14,55,65,28,39}
2、
0 1 2 3 4 5 6 7 8 9
14 22 39 43 55 65 73 81 93
28
{14,22,28,39,43,55,65,73,81,93}
*/
public class Radix_sort
{
public static void main(String[] args){
int[] arr = {73,22,93,43,55,14,28,65,39,81};
System.out.println(Arrays.toString(arr));
radix_sort(arr);
System.out.println(Arrays.toString(arr));
}
// 1 ， d 100
public static int getMaxDigit(int[] arr){
int d = 10;
for(int i = 0; i=d){
d *= 10;
}
}
return d;
}
public static void radix_sort(int[] arr){
int d = getMaxDigit(arr);
int n = 1;
int k = 0;// ， arr
int[][] bucket = new int[10][arr.length];// ，
int[] order = new int[arr.length];// ， 0
while(n /**
* Created by april on 2018/8/8.
* : ， ( 3 )
* A={2,5,3,0,2,3,0,3}
* 1、 A： 0 1 2 3 4 5 6 7
2 5 3 0 2 3 0 3
* 2、 5， C 6， 2 0，0 1，2 2，3 3，0 4，1 5.
C：0 1 2 3 4 5
2 0 2 3 0 1
*3、 C i C i
C：0 1 2 3 4 5
2 2 4 7 7 8
*4、 A B ， A， （ A 3 ）
（1）i=7 ，a[i]=3,c[3]=7,b[7-1]=b[6]=3,c[3]=c[3]-1
B: 0 1 2 3 4 5 6 7 C: 0 1 2 3 4 5
3 2 2 4 6 7 8
(2)i=6 ，a[i]=0，c[0]=2,b[2-1]=b[1]=0,c[0]=c[0]-1
B: 0 1 2 3 4 5 6 7 C: 0 1 2 3 4 5
0 3 1 2 4 6 7 8
......
*/
public class Count_sort
{
public static void main(String[] args){
int[] arr = {2,5,3,0,2,3,0,3};
System.out.println(Arrays.toString(arr));
int max = getMax(arr);
int[] B = count_sort(arr,max);// B
System.out.println(Arrays.toString(B));
}
// ， C
public static int getMax(int[] arr){
int max = arr[0];
for(int i=0;i=0;i--){// A
B[C[arr[i]]-1] = arr[i];//B
C[arr[i]]--;
}
return B;
}
} /**
* Created by april on 2018/8/8.
* ：O(N+n)，
*
* ：
* O（ + ）
* ( )， 0
* ， 1（ ）
* ， （ ）
*
* ： [0,1） n ，
n ， ，
， ，
:
A B
78 0
17 1 :12 :17
39 2 :21 :23 :26
26 3 :39
72 4
94 5
21 6 :68
12 7 :72 :78
23 8
68 9 :94
*/
public class Bucket_sort
{
public static void main(String[] args){
int[] arr = {78,17,39,26,72,94,21,12,23,68};
System.out.println(Arrays.toString(arr));
buck_sort(arr);
System.out.println(Arrays.toString(arr));
/* */
// int[] book = new int[101];
// for(int i = 0; i<=100; i++){
// book[i] = 0;
// }
// for(int i = 0;i=0;i--){//
// for(int k = 1;book[i]>=k;k++){// 1 ，
// System.out.print(i+" ");
// }
}
public static void buck_sort(int[] arr){
int bucknum = arr.length;
List> list = new ArrayList<>(bucknum);
for(int i = 0; i());
//
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int a : arr){
max = Math.max(max,a);
min = Math.min(min,a);
}
//
for(int a : arr){
int index = (int)((a - min)/(max+min+1.0)*arr.length);// 1 IndexOutOfBoundsEx
list.get(index).add(a);
}
//
for(int i = 0; i A : list){
for (int a : A){
arr[k++] = a;
}
}
}
}