preface
Internal sorting: the sorting of data stored in memory
External sorting: sorting data stored on external memory (such as disk and hard disk)
Seven sorts are based on comparison, and three sorts are based on non comparison.
1, Bubble sorting
1. Bubble sort is a stable sort. The idea is that traversing the array is to compare two adjacent elements. If the value is large, put it back. The result of one bubble sort is to put the largest value in the array at the back, and then the traversal length can be reduced.
2. The time complexity is O (n^2). In the best case, the array order time complexity is O (N) and the space complexity is O (1).
3. Optimization is to insert a variable to check whether the traversal has been exchanged. If there is no exchange, it means that it is in order.
public void bubbleSort(int []array){
//Bubble sorting is to move the maximum value to the last position every time
for(int i=0;i<array.length;i++){
boolean flg=true;
for(int j=0;j<array.length-i-1;j++){
if(array[j]>array[j+1]){
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
flg=false;
}
}
if(flg){
break;
}
}
}
2, Insert sort
1. Insert sorting is like playing cards. Insert the cards in your hand into the appropriate position. When sorting, first consider that the first element is in order, and then traverse and put other elements in the appropriate position,
2. The insertion sort time complexity is O (N^2), and the time complexity is O (1)
The code implementation is to take out the generation sort first, and then compare each subsequent element with it and put it in the appropriate position. By default, the first element is in order
public static void insertSort(int []array){
for(int i=1;i<array.length;i++){
int temp=array[i];
int j=i-1;
for(;j>=0;j--){
if(array[j]>temp){
array[j+1]=array[j];
}else {
//Because the previous elements are ordered, if the element is larger than the i-1 position element, its position is the appropriate position without sorting
break;
}
}
array[j+1]=temp;
}
}
1. Optimize insertion sorting
The optimization of insertion sorting is to find the position of the elements to be sorted, and quickly find the insertion position with binary search,
public static void insertSort(int []array) {
for (int i = 1; i < array.length; i++) {
int temp = array[i];
int left = 0;
int right = i;
while (left < right) {
int mid = (left + right) >> 1;
if (array[mid] < temp) {
left = mid + 1;
} else {
right = mid;
}
}
//The front elements are all in order. Then compare the elements to be sorted with the elements in the middle position to quickly find the position of generation sorting
for (int j = i; j > left; j--) {
array[j] = array[j - 1];
}
array[left] = temp;
}
}
3, Hill sort
In fact, Hill sort is the optimization of insertion sort, using the idea of grouping
For example, if you want to sort 10000 unordered data, the time complexity of inserting and sorting is O (10000 ^ 2)
But you group 10000 data into 100 groups and sort them in the group. O (100 ^ 2) * 100 groups are o (1000000) one million, which is much smaller than 100 million. This is the difference of 10000 data.
In general, the time complexity is O (N^1.3~1.5). In the worst case, the space complexity of O (N ^2) is O (1)
The most important thing is that the definition of increment is generally prime,
public static void shellSort(int []array,int gap){
for(int i=gap;i<array.length;i++){
int temp=array[i];
int j=i-gap;
for(;j>=0;j-=gap){
if(array[j]>temp){
array[j+gap]=array[j];
}else {
break;
}
}
array[j+gap]=temp;
}
}
4, Select sort
Selection sorting is also a simple sorting, that is, every time you traverse the array, put the smallest element in position i. after traversing the array, the first element is the smallest, and the second element is the second smallest. The smallest element in the sorting is in front. Of course, you can choose sorting or election.
Time complexity O (N^2) space complexity O(1)
public static void selectSort(int []array){
for(int i=0;i<array.length;i++){
for(int j=i+1;j<array.length;j++){
if(array[j]<array[i]){
int temp=array[j];
array[j]=array[i];
array[i]=temp;
}
}
}
}
5, Quick sort
Quick sort is to select a benchmark value and define double pointers. The right pointer looks for elements smaller than the benchmark value from the front, and the left pointer looks for elements larger than the benchmark value from the front to the back for exchange. Finally, put the benchmark value back. The elements on the left of the benchmark value are smaller than the benchmark value, and the elements on the right of the benchmark value are larger than the benchmark value. Recurse the left and right of the benchmark value respectively.
1. Basic quick sort
public static void quickSort(int []array,int low,int high){
if(low>=high){
return;
}
int left=low;
int right=high;
int base=array[low];
while(left!=right){
while(array[right]>=base&&left<right){
right--;
}
while(array[left]<=base&&left<right){
left++;
}
int temp=array[left];
array[left]=array[right];
array[right]=temp;
}
//Place the reference value in the appropriate position
array[low]=array[left];
array[left]=base;
quickSort(array,low,left-1);
quickSort(array,left+1,high);
}
2. Optimize quick sort
The optimization of quick sort is the selection of benchmark values. Generally, the optimization includes three numbers, middle and random benchmark values.
1. Three data extraction optimization
Compare the values of the left end, the right end and the middle position, and take the middle of the three numbers as the reference value to reduce the number of recursion.
public static void quickSort1(int[] array, int low, int high) {
//Fast scheduling in three data retrieval
if (low >= high) {
return;
}
int left = low;
int right = high;
//Put the middle value of the three numbers in the first position
//Set mid to the middle position
int num= choicmidenum(array, left, right);
int temp=array[num];
array[num]=array[left];
array[left]=temp;
int base=array[left];
while (left != right) {
while (array[right] >= base && left < right) {
right--;
}
while (array[left] <= base && left < right) {
left++;
}
int tem = array[left];
array[left] = array[right];
array[right] = tem;
}
//Place the reference value in the appropriate position
array[low] = array[left];
array[left] = base;
quickSort1(array, low, left - 1);
quickSort1(array, left + 1, high);
}
//Exchange values put the middle number first
public static int choicmidenum(int[] array, int begin, int end) {
int mid=(begin+end)>>1;
if(array[begin]>array[end]){
if(array[begin]<array[mid]){
return begin;
}else {
if(array[end]>array[mid]){
return end;
}else {
return mid;
}
}
}else {//begin<end
if(array[begin]>array[mid]){
return begin;
}else {//begin <mid
if(array[mid]>array[end]){
return mid;
}else {
return end;
}
}
}
}
This way of writing can effectively avoid the worst case, that is, recursion has only one branch.
3. Non recursive quick sorting
Fast sorting with stack
public static void quickSort(int []array){
//Non recursive quick sort
Stack<Integer> stack=new Stack<>();
int left=0;
int right=array.length-1;
int par=partion(array,left,right);
//1. Judge that there are more than two elements on the left
if(par>left+1){
stack.push(left);
stack.push(par);
}
if(par<right-1){
stack.push(par+1);
stack.push(right);
}
while(!stack.empty()){
right=stack.pop();
left=stack.pop();
par=partion(array,left,right);
if(par>left+1){
stack.push(left);
stack.push(par);
}
if(par<right-1){
stack.push(par+1);
stack.push(right);
}
}
}
public static int partion(int[] array,int start,int end) {
int tmp = array[start];
while (start < end) {
while (start < end && array[end] >= tmp) {
end--;
}
if(start >= end) {
array[start] = tmp;
break;
}else {
array[start] = array[end];
}
while (start < end && array[start] <= tmp) {
start++;
}
if(start >= end) {
array[start] = tmp;
break;
}else {
array[end] = array[start];
}
}
return start;
}
6, Heap sort
Heap sorting is to build the array into a large top heap, move the large value to the back, and then reduce the adjusted length by one.
public static int[] sortArray(int[] nums) {
createSort(nums);
int end=nums.length-1;
while(end>0){
int temp=nums[0];
nums[0]=nums[end];
nums[end]=temp;
//At this time, the maximum value is already in the last
adjust(nums,0,end);//The last value is not included in the adjustment
end--;
}
return nums;
}//Adjust reactor to large top reactor
public static void adjust(int []array,int parent,int len){
int child=2*parent+1;
while(child<len){
if(child+1<len&&array[child+1]>array[child]){
child++;
}
if(array[child]>array[parent]){
int temp=array[child];
array[child]=array[parent];
array[parent]=temp;
parent=child;
child=parent*2+1;
}else{
break;
}
}
}//Chuangdui
public static void createSort(int []array){
for(int i=(array.length-1-1)>>1;i>=0;i--){
adjust(array,i,array.length);
}
}
7, Merge sort
Merge sort is to divide the elements into small segments, then order the divided arrays, and finally order the whole.
public static void mergeSort(int []array,int low,int high){
if(low>=high){
return;
}
//decompose
int mid=(low+high)>>1;
mergeSort(array,low,mid);
mergeSort(array,mid+1,high);
//merge
merge(array,low,mid,high);
}
public static void merge(int []array,int low,int mid,int high){
int s1=low;
int s2=mid+1;
//Merge ordered arrays
int []newArray=new int[high-low+1];
int k=0;
while(s1<=mid&&s2<=high){
if(array[s1]<array[s2]){
newArray[k++]=array[s1++];
}else {
newArray[k++]=array[s2++];
}
}
while(s1<=mid){
newArray[k++]=array[s1++];
}
while(s2<=high){
newArray[k++]=array[s2++];
}
for(int i=0;i<newArray.length;i++){
array[i+low]=newArray[i];
}
}
1. Non recursive merge sort
//Non recursive merge sort
public static void mergeSort(int []array){
for(int gap=1;gap<array.length;gap*=2){
merge(array,gap);
}
}
public static void merge(int []array,int gap){
int []newArray=new int[array.length];
int k=0;
int s1=0;
int e1=s1+gap-1;
int s2=e1+1;
int e2=s2+gap-1>=array.length? array.length-1:s2+gap-1;
while(s2<array.length){
while(s1<=e1&&s2<=e2){
if(array[s1]<=array[s2]){
newArray[k++]=array[s1++];
}else {
newArray[k++]=array[s2++];
}
}
while(s1<=e1){
newArray[k++]=array[s1++];
}
while(s2<=e2){
newArray[k++]=array[s2++];
}
s1=e2+1;
e1=s1+gap-1;
s2=e1+1;
e2=s2+gap-1>=array.length? array.length-1:s2+gap-1;
}
while(s1<array.length){
newArray[k++]=array[s1++];
}
for(int i=0;i<newArray.length;i++){
array[i]=newArray[i];
}
}
8, Other sorting
1. Counting and sorting
It is applicable to scenes with large amount of data but small fluctuation range.
The idea is to create a counting array with the maximum number + 1, and then put the value in the position corresponding to the index of the array, that is, the number 59 will be put in the position of the array with the index of 59. If it is put in for the first time, it will be recorded as 1, and then add 1 every time to count the number. Finally, take out the position that is not 0 in the counting group and put it in a new array. For example, the index of counting array 0 is 3, Then put three zeros in the new array
The space complexity is O (N+K) and the time complexity is O (N+K). N is the length of the array and K is the length of the count array. Because the difference between the two is not very large, sometimes the time complexity and space complexity are also called o (n).
2. Cardinality sorting
Allocate buckets according to each digit of the key value, i.e
In the first round, the numbers are allocated according to each number, and the numbers are allocated to the corresponding bucket, and then the bucket is discharged according to the first in first out method
In the second round, the numbers are allocated according to ten digits, and the numbers are allocated to the corresponding bucket, and so on
The time complexity is O (N) and the space complexity is O (N).
3. Bucket sorting
To create a certain number of buckets, you can use an array or linked list to evenly distribute the elements to the corresponding buckets according to certain rules, then sort the elements in each bucket separately, and finally merge the non empty elements in the bucket into an orderly sequence.
9, Massive data sorting problem
A memory only 1G, now want to sort 40G files, how to achieve
1. First, the memory is far smaller than the file size, so you can only cut it first.
2. First divide the documents into 40 copies, and arrange each copy in order in the memory
3. Then merge and sort, select multiple files to read and sort in memory.
summary
The above is the seven comparison and sorting methods we have learned. Make a table to summarize them
| Sorting method | Best case | Worst case scenario | Average situation | Spatial complexity | stability |
|---|---|---|---|---|---|
| Bubble sorting | O(N) | O(N^2) | O(N^2) | O(1) | stable |
| Insert sort | O(N) | O(N^2) | O(N^2) | O(1) | stable |
| Shell Sort | O(N) | O(N^2) | O(N^1.3~1.5) | O(1) | instable |
| Select sort | O(N^2) | O(N^2) | O(N^2) | O(1) | instable |
| Quick sort | O(Nlog(N)) | O(N^2) | O(Nlog(N)) | O(logn~n) | instable |
| Merge sort | O(Nlog(N)) | O(Nlog(N)) | O(Nlog(N)) | O(N) | instable |
| Heap sort | O(Nlog(N) | O(Nlog(N) | O(Nlog(N) | O(1) | instable |
