c language 5 commonly used sorting algorithm example code

1. Insertion sort

Basic idea: Insertion sort means that at each step, one piece of data to be sorted is inserted into the appropriate place in the sorted data according to its size until all insertions are completed.

void insertSort(vector<int>& nums)
{
  int k = 0;
  for (int i = 0; i < nums.size(); ++i)
  {
    int temp = nums[i];
    int j = i;
    for (; j > 0 && temp < nums[j-1]; --j)
      nums[j] = nums[j-1];
    nums[j] = temp;
  }
}

2. Hill sort

Basic idea: the first row element sequence is divided into several sub sequence (composed of elements separated by a "delta") direct insertion sort, respectively, and then in turn to cut incremental sort, for the entire sequence of elements in the basic order (increment is small enough, again to all the elements in one direct insertion sort. Because the efficiency of direct insertion sort is high when the elements are basically ordered (close to the best case), the time efficiency of Hill sort is greatly improved compared with the previous two methods.

void shellSort(vector<int>& nums)
{
  for (int gap = nums.size() / 2; gap > 0; gap /= 2)
  {
    for (int i = gap; i < nums.size(); ++i)
    {
      int temp = nums[i];
      int j = i;
      for (; j >=gap && temp < nums[j-gap]; j -= gap)
        nums[j] = nums[j - gap];
      nums[j] = temp;
    }
  }
}

3. The heap sort

In 1 sentence summary, pile is a kind of improved selection, improvement is that every time to make a choice, not only the largest number selected, and the 1 some operation in the process of sorting the records, it can use in the subsequent order, and have a group of thoughts in it, so as to improve the sorting efficiency, its efficiency is O (n * logn).

#include<stdio.h> 
int c=0;
/*heapadjust() The function of a function is to implement the a[m] to a[n] Is adjusted to meet the characteristics of the large top heap */
/*a[] Is the array to be processed, m It's the starting coordinate,  n Is the terminating coordinate */
void heapadjust(int a[], int m, int n) 
{
	int i, temp;
	temp=a[m];
	for (i=2*m;i<=n;i*=2)// from m The left child begins  
	{
		if(i+1<=n && a[i]<a[i+1])// If the left child is smaller than the right child, will i++ So that the i The value of mu is the lower value of the largest child  
		{
			i++;
		}
		if(a[i]<temp)// If the oldest child is less than temp , do nothing, exit the loop; Otherwise the exchange a[m] and a[i] I'm going to put the maximum value here a[i] place  
		{
			break;
		}
		a[m]=a[i];
		m=i;
	}
	a[m]=temp;
}
void crtheap(int a[], int n)// Initialize creation 1 A big heap  
{
	int i;
	for (i=n/2; i>0; i--)//n/2 For the final 1 Two parent nodes, in turn forward to establish the large top heap  
	{
		heapadjust(a, i, n);
	}
}
/*swap() The delta function is the delta function a[i] and a[j] swap */
void swap(int a[], int i, int j) 
{
	int temp;
	temp=a[i];
	a[i]=a[j];
	a[j]=temp;
	c++;
}
void heapsort(int a[], int n) 
{
	int i;
	crtheap(a, n);
	for (i=n; i>1; i--) 
	{
		swap(a, 1, i);
		// Will be the first 1 The number, that's the number from a[1] to a[i] The largest number in, put in a[i] The location of the  
		heapadjust(a, 1, i-1);
		// For the rest of the a[1] to a[i] , do heap sort again, pick the largest value and put it in a[1] The location of the 
	}
}
int main(void) 
{
	int i;
	int a[10]={-1,5,2,6,0,3,9,1,7,4};
	printf(" Before ordering: ");
	for (i=1;i<10;i++) 
	{
		printf("%d",a[i]);
	}
	heapsort(a, 9);
	printf("\n\n Co-exchange data %d time \n\n", c);
	printf(" After the order: ");
	for (i=1;i<10;i++) 
	{
		printf("%d",a[i]);
	}
	printf("\n\n\n");
	return 0;
}

4. Merge sort

Basic idea: Merge sort USES recursive and divide-and-conquer techniques to divide data sequences into smaller and smaller semi-subtables, then sorts the semi-subtables, and finally merges the sorted semi-subtables into larger and larger ordered sequences using recursive steps. Merge sort includes two steps, respectively:

1) Plot the numerator
2) Merge half subtables

So leetcode youdao, merge sort, sort list

class Solution {
public:
 // Merge sort 
  ListNode* getMiddleOfList(ListNode* head)
  {
    ListNode* mid = head;
    ListNode* last = head;
    while (last->next!=NULL&&last->next->next!=NULL)
    {
      mid = mid->next;
      last = last->next->next;
    }
    return mid;
  }
  ListNode* sortList(ListNode* head) {
    if (head == NULL || head->next == NULL)return head;
    ListNode* mid = getMiddleOfList(head);
    ListNode* midnext = mid->next;
    mid->next = NULL;
    return mergeList(sortList(head), sortList(midnext));
  }
  ListNode* mergeList(ListNode* a, ListNode* b)
  {
    ListNode* res = new ListNode(-1);
    ListNode* cur = res;
    while (a != NULL&&b != NULL)
    {
      if (a->val < b->val)
      {
        cur->next = a;
        a = a->next;
      }
      else
      {
        cur->next = b;
        b = b->next;
      }
      cur = cur->next;
    }
    cur->next = a != NULL ? a : b;
    return res->next;
  }
};

5. Quicksort

Basic idea: the first row element sequence is divided into several sub sequence (composed of elements separated by a "delta") direct insertion sort, respectively, and then in turn to cut incremental sort, for the entire sequence of elements in the basic order (increment is small enough, again to all the elements in one direct insertion sort. Because the efficiency of direct insertion sort is high when the elements are basically ordered (close to the best case), the time efficiency of Hill sort is greatly improved compared with the previous two methods.

class sort {
public:
  int median3(vector<int>& nums, int left, int right)
  {
    int mid = (left + right) / 2;
    if (nums[left] > nums[mid])swap(nums[left], nums[mid]);
    if (nums[mid] > nums[right])swap(nums[mid], nums[right]);
    if (nums[left] > nums[mid])swap(nums[left], nums[mid]);

    swap(nums[mid], nums[left]);
    return nums[left];
  }
  void quickSort(vector<int>& nums, int i, int j)
  {
    if (i > j)return;
    int partition = median3(nums, i, j);
    int low = i+1, high = j;
    while (low < high)
    {
      while (nums[low] < partition)low++;     
      while (nums[high] > partition)high--;
      if (low < high)swap(nums[low], nums[high]);
      else
        break;
    }
    swap(nums[i], nums[high]);
    quickSort(nums, i, high - 1);
    quickSort(nums, high + 1, j);
  }
  void qs(vector<int>& nums)
  {
    quickSort(nums, 0, nums.size() - 1);
  }
};

conclusion

Above is the text on c language 5 commonly used sorting algorithm example code, hope to help you. Interested friends can continue to refer to other related topics in this site, if there is any deficiency, welcome to comment out. Thank you for your support!