C language to achieve eight sorts (2)

2. Exchange sort

 

2.1 Bubble sort

What is bubble sorting ？

Bubble sort （Bubble Sort） It is also a simple and intuitive sorting algorithm .

It repeatedly visits the sequence to be sorted , Compare two elements at a time , If they're in the wrong order, exchange them . The job of the interview sequence is to repeat until there is no need to exchange , That is to say, the sequence has been sorted .

The name of this algorithm comes from the fact that the smaller the elements, the more slowly “ floating ” Go to the top of the list .

The code implementation is as follows :

void BubbleSort(int *a,int length){
	int i,j;
	int flag=1; // Determine whether to cycle 
	for(i=0;i<length-1&&flag==1;i++){
		for(j=0;j<length-1-i;j++){
			flag=0;
			if(a[j]>a[j+1]){
				flag=1;
				int temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		}
	}
}

However, due to the high time complexity of bubble sorting , All this leads to a new sort of sorting -- Quick sort （QuickSort）.

The name can show its speed .

How is this sort realized ？

The code is as follows :

// Quick sort  
int Partition(int*a,int left,int right){
	int temp=a[left];//left Subscript as reference number 
	while(left<right){
		while(left<right&&a[right]>temp){
			right--;
		}
		if(left<right){
			a[left]=a[right];
		}
		while(left<right&&a[left]<temp){
			left++;
		}
		if(left<right){
			a[right]=a[left];
		}
	} 
	a[right]=temp;
	return right;
}
void QuickSort(int*a,int left,int right){
	if(left<right){
		int pivot=Partition(a,left,right);
		QuickSort(a,left,pivot-1);
		QuickSort(a,pivot+1,right);
	}
}

We first choose one as the reference number , And then iterate through the entire array （ In addition to the benchmark ）, Place less than the reference number on its left , Those larger than the reference number are placed on its right .

Then the left and right sides of the reference number are regarded as an array , Repeat the above operation , Until there is only one element left in each array .

---

Let me have another water