sort has always been a headache for me to do, before the "data structure" soy sauce to go, the whole semester barely able to write a bubble sort. To prepare for the second half of the work, and also know the importance of sorting algorithms (said to be interviewing the knowledge necessary to ask), so it took some time to re-examine a bit.
sort can be divided into two broad categories: internal sorting and external sorting. In the sorting process, all records stored in memory, it is called within the sort, if the sorting process requires the use of external memory, it is called external sorting. Here to talk belong within the sort order.
sort there can be divided into the following categories within:
(1), insertion sort: direct insertion sort, dichotomy insertion sort, shell sort.
(2), selection sort: simple selection sort, heap sort.
(3), exchange Sort by: bubble sort, quick sort.
(4), merge sort
(5), radix sort
one, insertion sort
? direct insertion sort (from back to front to find a suitable location, insert)
1, the basic idea: each step will be a record to be sorted according to their order code size has already been sorted into the appropriate location sequence of words (from the back to the ago to find a suitable location), until all insertion sort last.
2, Example
3, java realize
1 package com.sort;
2
3 public class ?????? {
4
5 public static void main(String[] args) {
6 int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1};
7 System.out.println("?????");
8 for (int i = 0; i < a.length; i++) {
9 System.out.print(a[i]+" ");
10 }
11 //??????
12 for (int i = 1; i < a.length; i++) {
13 //?????
14 int temp = a[i];
15 int j;
16 /*for (j = i-1; j>=0 && a[j]>temp; j--) {
17 //???temp???????
18 a[j+1] = a[j];
19 }*/
20 for (j = i-1; j>=0; j--) {
21 //???temp???????
22 if(a[j]>temp){
23 a[j+1] = a[j];
24 }else{
25 break;
26 }
27 }
28 a[j+1] = temp;
29 }
30 System.out.println();
31 System.out.println("?????");
32 for (int i = 0; i < a.length; i++) {
33 System.out.print(a[i]+" ");
34 }
35 }
36
37 }
4, analysis
direct insertion sort is stable sort. Stability analysis on a variety of algorithms can refer http://www.cnblogs.com/ Braveliu/archive/2013/01/15/2861201.html
file is not the same initial state, directly into the sort of time-consuming are very different. If the initial state is positive sequence file, each record to be inserted only need to compare one will be able to find a suitable place to insert, so the time complexity of the algorithm is O (n), then the best case. If the initial state is in reverse order, then the first i need to compare the records to be inserted i +1 times in order to find a suitable location inserted, so the time complexity is O (n 2 ), then the worst case.
direct insertion sort, the average time complexity is O (n2).
? dichotomy insertion sort (by dichotomy to find a suitable insert)
1, the basic idea: insertion sort dichotomy of thought and directly into the same, only to find a suitable insertion position in different ways, according to the dichotomy here is to find a suitable location, You can reduce the number of comparisons.
2, Example
3, java realize
1 package com.sort;
2
3 public class ?????? {
4 public static void main(String[] args) {
5 int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1};
6 System.out.println("?????");
7 for (int i = 0; i < a.length; i++) {
8 System.out.print(a[i]+" ");
9 }
10 //??????
11 sort(a);
12 System.out.println();
13 System.out.println("?????");
14 for (int i = 0; i < a.length; i++) {
15 System.out.print(a[i]+" ");
16 }
17 }
18
19 private static void sort(int[] a) {
20 for (int i = 0; i < a.length; i++) {
21 int temp = a[i];
22 int left = 0;
23 int right = i-1;
24 int mid = 0;
25 while(left<=right){
26 mid = (left+right)/2;
27 if(temp<a[mid]){
28 right = mid-1;
29 }else{
30 left = mid+1;
31 }
32 }
33 for (int j = i-1; j >= left; j--) {
34 a[j+1] = a[j];
35 }
36 if(left != i){
37 a[left] = temp;
38 }
39 }
40 }
41 }
4, analysis
course, the dichotomy insertion sort is stable.
two minutes into the sort of comparisons with the initial state records to be sorted nothing depends only on the number of records. When n is large, the maximum insertion sort than direct comparisons much less. But greater than the minimum direct insertion sort comparisons. Algorithm mobile number and directly into the same sort algorithm, the worst case is n2 / 2, the best case is n, the average number of moves is O (n2).
? Hill sorting
1, the basic idea: first take an integer less than n d1 as the first increment , all records in the file into d1 groups. All multiples of d1 distance record in the same group. First within each group direct insertion sort ; Then, take the second incremental d2 < ; d1 Repeat the above grouping and sorting, until taken incremental dt = 1 (dt
2, Example
3, java realize
1 package com.sort;
2
3 //???
4 public class ???? {
5
6
7 public static void main(String[] args) {
8 int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1};
9 System.out.println("?????");
10 for (int i = 0; i < a.length; i++) {
11 System.out.print(a[i]+" ");
12 }
13 //????
14 int d = a.length;
15 while(true){
16 d = d / 2;
17 for(int x=0;x<d;x++){
18 for(int i=x+d;i<a.length;i=i+d){
19 int temp = a[i];
20 int j;
21 for(j=i-d;j>=0&&a[j]>temp;j=j-d){
22 a[j+d] = a[j];
23 }
24 a[j+d] = temp;
25 }
26 }
27 if(d == 1){
28 break;
29 }
30 }
31 System.out.println();
32 System.out.println("?????");
33 for (int i = 0; i < a.length; i++) {
34 System.out.print(a[i]+" ");
35 }
36 }
37
38 }
4, analysis
We know that onceinsertion sort is stable, but in a different insertion sorting process, the same element may insertion sort in their move, and finally its stability will be disrupted, so Hill sorting is unstable .
Hill sort of time better than direct insertion sort, for the following reasons:
1 package com.sort;
2
3 //???
4 public class ??????? {
5
6 public static void main(String[] args) {
7 int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
8 System.out.println("?????");
9 for (int i = 0; i < a.length; i++) {
10 System.out.print(a[i]+" ");
11 }
12 //???????
13 for (int i = 0; i < a.length; i++) {
14 int min = a[i];
15 int n=i; //??????
16 for(int j=i+1;j<a.length;j++){
17 if(a[j]<min){ //??????
18 min = a[j];
19 n = j;
20 }
21 }
22 a[n] = a[i];
23 a[i] = min;
24
25 }
26 System.out.println();
27 System.out.println("?????");
28 for (int i = 0; i < a.length; i++) {
29 System.out.print(a[i]+" ");
30 }
31 }
32
33 }
4, analysis
simple selection sort is unstable sort.
time complexity: T (n) = O (n2).
? heap sort
1, the basic idea:
heap sort is a tree selection sort, selection sort is directly effective improvements.
heap definition: a sequence of n elements (h1, h2, ..., hn), if and only if (hi> = h2i, hi> = 2i +1) or (hi <= h2i , hi <= 2i +1) (i = 1,2, ..., n / 2) is called the heap. Discussed here only to meet the former condition of the heap. As can be seen from the definition of the heap, stack top element (ie the first element) will be for the largest item (big top heap). Complete binary tree can be very visually represent the structure of the heap. Top of the heap is the root, the other for the left subtree and right subtree.
idea: the initial sequence of numbers to be sorted is stored as a binary sequence, adjust their memory sequence, to become a heap, the heap when the maximum number of the root node. Then the root node and the last node in the heap exchange. Then the previous (n-1) of a number of re-adjustment of the heap. And so on, until only two nodes of the heap, and in exchange they finally got there an ordered sequence of n nodes. From the algorithm description, heap sort requires two processes, one is to establish the heap, two heaps are top of the heap with the last element of swap positions. So there are two functions composed heap sort. First, the construction of the heap penetration function, the second is called repeatedly penetration function implements sorting function.
2, Example
initial sequence: 46,79,56,38,40,84
construction of the heap:
exchange kicked out from the heap maximum number
followed by analogy: the last heap last remaining two nodes exchange, kicked one, sorting is completed.
3, java realize
1 package com.sort;
2 //???
3 import java.util.Arrays;
4
5 public class HeapSort {
6 public static void main(String[] args) {
7 int[] a={49,38,65,97,76,13,27,49,78,34,12,64};
8 int arrayLength=a.length;
9 //????
10 for(int i=0;i<arrayLength-1;i++){
11 //??
12 buildMaxHeap(a,arrayLength-1-i);
13 //???????????
14 swap(a,0,arrayLength-1-i);
15 System.out.println(Arrays.toString(a));
16 }
17 }
18 //?data???0?lastIndex????
19 public static void buildMaxHeap(int[] data, int lastIndex){
20 //?lastIndex?????????????????
21 for(int i=(lastIndex-1)/2;i>=0;i--){
22 //k?????????
23 int k=i;
24 //????k????????
25 while(k*2+1<=lastIndex){
26 //k??????????
27 int biggerIndex=2*k+1;
28 //??biggerIndex??lastIndex??biggerIndex+1???k?????????
29 if(biggerIndex<lastIndex){
30 //??????????
31 if(data[biggerIndex]<data[biggerIndex+1]){
32 //biggerIndex????????????
33 biggerIndex++;
34 }
35 }
36 //??k???????????????
37 if(data[k]<data[biggerIndex]){
38 //????
39 swap(data,k,biggerIndex);
40 //?biggerIndex??k???while?????????????k??????????????
41 k=biggerIndex;
42 }else{
43 break;
44 }
45 }
46 }
47 }
48 //??
49 private static void swap(int[] data, int i, int j) {
50 int tmp=data[i];
51 data[i]=data[j];
52 data[j]=tmp;
53 }
54 }
4, analysis
heap sort is a stable sorting algorithm.
superior to simple selection sort heap sort reasons:
Direct selection sort, in order from the R [1 .. n] selected keyword smallest records must be n-1 times then compared in a R [2 .. n] smallest selected keyword recording, and to do n-2 comparisons. Indeed, the latter n-2 times a comparison, there are many more likely in the previous n-1 times a comparison has been done, but the former is not retained when a trip sorting results of these comparisons, the sorting time and repeated after a trip performed these comparison operations.
Heap sort tree structure can save part of the comparison result, can reduce the number of comparisons.
heap sort worst time complexity is O (nlogn) . Heap sequence closer to the average performance of the worst performance. Since comparisons needed to build the initial heap more frequently, so the number of records heap sort unsuitable for fewer files.
three exchange sort
? bubble sort
1, the basic idea: to be sorted in a number of groups in the current has not yet sorted the full range of numbers, from top to bottom on two adjacent numbers in order to compare and adjust so than large numbers sinking, taking up less. Namely: Whenever two adjacent few find their sort after comparing and sorting requirements reversed, they will be interchangeable.
2, Example
3, java realize
1 package com.sort;
2
3 //??
4 public class ???? {
5 public static void main(String[] args) {
6 int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
7 System.out.println("?????");
8 for (int i = 0; i < a.length; i++) {
9 System.out.print(a[i]+" ");
10 }
11 //????
12 for (int i = 0; i < a.length; i++) {
13 for(int j = 0; j<a.length-i-1; j++){
14 //??-i?????????????i??????????????????
15 if(a[j]>a[j+1]){
16 int temp = a[j];
17 a[j] = a[j+1];
18 a[j+1] = temp;
19 }
20 }
21 }
22 System.out.println();
23 System.out.println("?????");
24 for (int i = 0; i < a.length; i++) {
25 System.out.print(a[i]+" ");
26 }
27 }
28 }
4, analysis
bubble sort is a stable sorting method.
package com.sort;
//???
public class ???? {
public static void main(String[] args) {
int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
System.out.println("?????");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
//????
quick(a);
System.out.println();
System.out.println("?????");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
}
private static void quick(int[] a) {
if(a.length>0){
quickSort(a,0,a.length-1);
}
}
private static void quickSort(int[] a, int low, int high) {
if(low<high){ //???????????????????????
int middle = getMiddle(a,low,high);
quickSort(a, 0, middle-1);
quickSort(a, middle+1, high);
}
}
private static int getMiddle(int[] a, int low, int high) {
int temp = a[low];//????
while(low<high){
//?????????????
while(low<high && a[high]>=temp){
high--;
}
a[low] = a[high];
while(low<high && a[low]<=temp){
low++;
}
a[high] = a[low];
}
a[low] = temp;
return low;
}
}
4, analysis
quicksort is unstable sort.
quicksort time complexity is O (nlogn).
when n is large parallelism better use of fast, when the sequence is basically an orderly row with fast but not good.
four, merge sort
1, the basic idea: Merge (Merge) is a sort of two (or more) into a new sorted list ordered list, that is the sequence to be sorted into several sub-sequences, each subsequence are ordered. Then put into an ordered subsequence overall orderly sequence.
2, Example
3, java realize
1 package com.sort;
2
3 //??
4 public class ???? {
5 public static void main(String[] args) {
6 int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
7 System.out.println("?????");
8 for (int i = 0; i < a.length; i++) {
9 System.out.print(a[i]+" ");
10 }
11 //????
12 mergeSort(a,0,a.length-1);
13 System.out.println();
14 System.out.println("?????");
15 for (int i = 0; i < a.length; i++) {
16 System.out.print(a[i]+" ");
17 }
18 }
19
20 private static void mergeSort(int[] a, int left, int right) {
21 if(left<right){
22 int middle = (left+right)/2;
23 //???????
24 mergeSort(a, left, middle);
25 //???????
26 mergeSort(a, middle+1, right);
27 //??
28 merge(a,left,middle,right);
29 }
30 }
31
32 private static void merge(int[] a, int left, int middle, int right) {
33 int[] tmpArr = new int[a.length];
34 int mid = middle+1; //???????
35 int tmp = left;
36 int third = left;
37 while(left<=middle && mid<=right){
38 //??????????????????
39 if(a[left]<=a[mid]){
40 tmpArr[third++] = a[left++];
41 }else{
42 tmpArr[third++] = a[mid++];
43 }
44 }
45 //????????????
46 while(left<=middle){
47 tmpArr[third++] = a[left++];
48 }
49 while(mid<=right){
50 tmpArr[third++] = a[mid++];
51 }
52 //???????????
53 while(tmp<=right){
54 a[tmp] = tmpArr[tmp++];
55 }
56 }
57 }
4, analysis
merge sort is stable sorting method.
merge sort time complexity is O (nlogn).
rate second only to quickly sort, stable sorting algorithm, commonly used for the overall disorder, but each child a relatively orderly sequence.
five, radix sort
1, the basic idea: all the values ??to be compared (positive integer) uniform for the same number of bit length, the number of digital short leading zeros. Then, beginning from the lowest, followed by once sorted. This sort from the lowest to the highest bit sorting is completed, the series becomes an ordered sequence.
2, Example
3, java realize
1 package com.sort;
2
3 import java.util.ArrayList;
4 import java.util.List;
5 //??
6 public class ???? {
7 public static void main(String[] args) {
8 int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1};
9 System.out.println("?????");
10 for (int i = 0; i < a.length; i++) {
11 System.out.print(a[i]+" ");
12 }
13 //????
14 sort(a);
15 System.out.println();
16 System.out.println("?????");
17 for (int i = 0; i < a.length; i++) {
18 System.out.print(a[i]+" ");
19 }
20 }
21
22 private static void sort(int[] array) {
23 //?????????????
24 int max = 0;
25 for (int i = 0; i < array.length; i++) {
26 if(max<array[i]){
27 max = array[i];
28 }
29 }
30 //????
31 int times = 0;
32 while(max>0){
33 max = max/10;
34 times++;
35 }
36 //??????
37 List<ArrayList> queue = new ArrayList<ArrayList>();
38 for (int i = 0; i < 10; i++) {
39 ArrayList queue1 = new ArrayList();
40 queue.add(queue1);
41 }
42 //??times??????
43 for (int i = 0; i < times; i++) {
44 //??
45 for (int j = 0; j < array.length; j++) {
46 int x = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
47 ArrayList queue2 = queue.get(x);
48 queue2.add(array[j]);
49 queue.set(x,queue2);
50 }
51 //??
52 int count = 0;
53 for (int j = 0; j < 10; j++) {
54 while(queue.get(j).size()>0){
55 ArrayList<Integer> queue3 = queue.get(j);
56 array[count] = queue3.get(0);
57 queue3.remove(0);
58 count++;
59 }
60 }
61 }
62 }
63 }
4, analysis
radix sort is stable sorting algorithm.
radix sort time complexity is O (d (n + r)), d is the median, r is the base.
Summary:
a stability:
Stabilization: bubble sort, insertion sort, merge sort, and radix sort
unstable: selection sort, quick sort, shell sort, heap sort
Second, the average time complexity
O (n ^ 2): direct insertion sort, simple selection sort, bubble sort.
smaller scale in the data (9W inside), direct insertion sort, selection sort almost simple. When the data is large, the bubble sort algorithm's time costliest. performance is O (n ^ 2) algorithm is basically compares adjacent elements are basically stable .
O (nlogn): quick sort, merge sort, shell sort, heap sort.
where fast row is the best, followed by the merging and Hill, heap sort in the large amount of data significantly.
three, sorting algorithm selection
1. data smaller
(1) the basic sequence to be sorted out in the case, you can choose direct insertion sort ;
(2) is not required for stability is preferable simple selection sort , on the stability requirements appropriate to insert or bubbling
2. data size is not large
(1) can use memory space, disorderly sequence of stability is not required, quick sort , this Time to pay log (N) additional space.
(2) may be ordered sequence itself on stability requirements, space permitted, to use merge sort
3. data is large
(1) on the stability requirements, you can consider merge sort .
(2) on the stability did not ask, it is appropriate heap sort
4. initial basic orderly sequence (positive sequence), to use the direct insertion, bubble
References:
http://blog.csdn.net/without0815/article/details/7697916
没有评论:
发表评论