Summary of Classical Sorting

Bubble sorting (stable)
Compare the two adjacent elements in turn, and change the big ones to the back. The result of a cycle is that the largest number is at the end. Repeat the above steps (except the last one) until you have finished.

  • Average time complexity: O (n^2)
  • Optimal time complexity: O(n)
void bubble_sort(vector<int>&nums)
{
	int len=nums.size();
	for(int i=0;i<len;i++)
	{
		for(int j=0;j<len-i-1;j++)
		{
			if(nums[j]>nums[j+1])swap(nums[j],nums[j+1]);
		}
	}
}

Selective Sorting

  • Simple Selection Sorting (Unstable)
    Choose the smallest one in the sequence, insert it in the first place, and so on.

  • The number of times that n numbers need to be compared is n(n-1)/2

  • Time complexity is O(n^2)

  • The time complexity of mobile operation is O(n)

void select_sort(vector<int>&nums)
{
	int len=nums.size();
	for(int i=0;i<len;i++)
	{
		int temp=i;
		for(int j=i;j<len;j++)
		{
		if(nums[temp]>nums[j])temp=j;
		}
		swap(nums[i],nums[temp]);
	}
}
  • Heap sorting

Insertion sort

  • Direct insertion sort (stable)
    The records to be sorted are inserted into an ordered sequence one by one according to the size of their key code values until all the records are inserted.

  • Average Time Complexity O(n^2)

  • Spatial complexity O(1)

void insert_sort(vector<int>&nums)
{
	int len=nusms.size();
	for(int i=1;i<len;i++)
	{
		int temp=nums[i];
		int j=i;
		while(j>=1&&temp<nums[j-1])
		{
			nums[j]=nums[j-1];
			j--;
		}
		nums[j]=temp;
	}
}
  • Binary Insertion Sort
    In direct insertion sort, it is very inefficient to compare the insertion elements with the existing ordered sequence elements at one time.
    Half-fold insertion, using half-fold search method to find the insertion point location, can reduce the number of comparisons, but the number of moves unchanged, time and space complexity and direct insertion sort, in the case of more elements can improve the search performance.
void insert_sort(vector<int>&nums)
{
	int len=nums.size();
	for(int i=1;i<len;i++)
	{
		int temp=nums[i];
		int pre=0;
		int end=i-1;
		int mid;
		while(pre<=end)
		{
			mid=(pre+end)/2;
			if(nums[mid]>temp)end=mid-1;
			else if(nums[mid]<=temp)pre=mid+1;
		}
		for(int j=i;j>=pre+1;j--)
            nums[j]=nums[j-1];
            nums[pre]=temp;
	}
}

Quick sort
Partition method

public static int partition(int[] array, int lo,int hi){
	int key=array[lo];
	int i=lo;
	int j=hi;
	while(i<j){
		while(array[j]>=key&&i<j)j--;
		while(array[i]<=key&&i<j)i++;
		swap(array,i,j);
}
	swap(array,lo,j);
	return j;
}

Using swap () function, we must write more than key in front and less than key in back, so that we can ensure that when we show off the first while loop in exit, the current j must point to the number less than key value, so that we can finally exchange the value with key value.

Shell Sort
Namely, reduce the incremental sorting, insert all the numbers into the sorting according to certain incremental grouping, reduce the incremental repetition of the above actions until the end of the increment 1.

  • When insertion sort is used to manipulate almost ordered data, the efficiency of insertion sort is high, and the efficiency of linear sort can be achieved.

  • But insertion sort is generally inefficient, because insertion sort can only move data one bit at a time.

void ShellSort(int array[])
{
	int i,j;
	int temp;//Defined temporary variables
for(int step=length/2;step>0;step/=2)//Step is the step size and reduces it by half each time in the loop
{
	for(i=step;i<LENGTH;i++)
	{
		temp=array[i];//Save elements traversed each time to prepare for insertion sort later
		for(j=i-step;(j>=0&&array[j]>temp);j-=step)//The end condition of traversal is to subscribe "0" or not satisfy the rule (ascending order, descending order).
		{
			array[j+step]=array[j];
		}
		array[j+step]=temp;//Finally, put the temporary variable in its corresponding position.
	}
}
}

Merge Sort
Merge sorting is an effective sorting algorithm created in merge operation. This algorithm is a very typical application of Divide and Conquer, and divide and conquer recursion can be carried out at the same time.
1. Iterative implementation:

Realization principle:

(1) The application space, which is the sum of two sorted sequences, is used to store the merged sequences.

(2) Set two pointers at the beginning of two sorted sequences.

(3) Compare the elements pointed by the two pointers, select the relatively small elements into the merge space, and move the pointer to the next position.

Repeat step 3 until a pointer reaches the end of the sequence

Copy all the remaining elements of another sequence directly to the end of the merged sequence

void merge_sort(vector<int>&nums)
    {
        int len=nums.size();
        int result[len];
        int i;
        for(int blocks=1;blocks<len;blocks*=2)
        {
            i=0;
        for(int start=0;start<len;start+=2*blocks)
        {
            int start1=start;
            int end1=(start+blocks)>len?len:start+blocks;
            int start2=end1;
            int end2=(start2+blocks)>len?len:start2+blocks;
            while(start1<end1&&start2<end2)
            {
                if(nums[start1]<nums[start2])
                {
                    result[i++]=nums[start1];
                    start1++;
                }
                 else if(nums[start1]>=nums[start2])
                {
                    result[i++]=nums[start2];
                    start2++;
                }
            }
            while(start1<end1)
            {
                result[i++]=nums[start1++];
            }
            while(start2<end2)
            {
                result[i++]=nums[start2++];
            }
            
                
        }
            for(int i=0;i<len;i++)
            nums[i]=result[i];
        }
           
        
    }

2. Recursive Implementation

Assuming that a sequence has n elements

(1) The sequence is merged with two adjacent digits to form floor(n/2) sequences. After sorting, each sequence contains two elements.

(2) Merge the above sequences again to form floor(n/4) sequences, each of which contains four elements.

Repeat step 2 until all elements are sorted.
Code:

void merge_sort(vector<int>&nums,int*result,int start,int end)
    {
        if(start>=end)return;
        int len=end-start;
        int start1=start;
        int end1=start+len/2;
        int start2=end1+1;;
        int end2=end;
        merge_sort(nums,result,start1,end1);
        merge_sort(nums,result,start2,end2);
        int i=start;
        while(start1<end1+1&&start2<end2+1)
            {
                if(nums[start1]<=nums[start2])
                {
                    result[i++]=nums[start1];
                    start1++;
                }
                 else if(nums[start1]>nums[start2])
                {
                    result[i++]=nums[start2];
                    start2++;
                }
            }
            while(start1<end1+1)
            {
                result[i++]=nums[start1++];
            }
            while(start2<end2+1)
            {
                result[i++]=nums[start2++];
            }
            for(int i=start;i<=end;i++)
            nums[i]=result[i];
            
        
    }

Reference:
1 https://blog.csdn.net/marcosyw/article/details/72794216
2 https://blog.csdn.net/hlang8160/article/details/78940780
3 https://www.cnblogs.com/bulingpan/p/6416351.html

Tags: less Mobile shell

Posted on Mon, 05 Aug 2019 22:45:29 -0700 by ec