各种排序算法

插入排序

• 核心思想：一次选取一个元素作为tem,然后让其与它前面的数组从后向前依次进行比较，直到找到tem需要插入的位置，然后插入进去

• void InsertSort(int* a, int n) {
  	for (int i = 1; i < n; i++) {
  		int end = i - 1;
  		int tem = a[i];
  		while (end >= 0) {
  			if (tem < a[end]) {
  				a[end + 1] = a[end];
  				end--;
  			}
  			else {
  				break;
  			}
  		}
          //当代码进行到这里，有两种情况：
          //一种是此时tem>=a[end],即tem应该插入到end这个下标后面
          //第二种是此时end==-1,也就是说此时tem比数组里所有元素都小，应该插入到开头
          //无论是哪一种情况，均是把tem插入到下标为end+1的位置
  		a[end + 1] = tem;
  	}
  }
  

希尔排序

• 核心思想：因为插入排序对于接近有序的数组进行排序是非常快的，所以希尔排序是在直接插入排序的前面加上一个预排序的过程，也就是说先经过一个预排序让数组接近有序，然后在使用直接插入排序

• 对于预排序：其实是一种分组插排，也就是将间隔为gap的分为一个小组，gap的数值是多少，整个数组就会被分为gap个小组，然后对于每个小组内部进行直接插入排序。gap越大，大的数字越容易到后边，gap越小，越精确。所以gap应该是一个由大变小的数，也就意味这预排序不只进行一轮，而是对于每一个gap都进行一次，因为任何数字在除二的最后都会1，而当gap1时，就相当于进行了一个直接插入排序，即核心思想里面的第二步

• 代码一：(先排好一个小组，在开始排下一个小组)

• void ShellSort(int* a, int n) {
  	int gap = n;
  	while (gap > 1) {
  		gap /= 2;
  		for (int j = 0; j < gap; j++) {
  			for (int i = j; i < n - gap; i += gap) {
  				int end = i;
  				int tem = a[i + gap];
  				while (end >= 0) {
  					if (tem < a[end]) {
  						a[end + gap] = a[end];
  						end -= gap;
  					}
  					else {
  						break;
  					}
  				}
  				a[end + gap] = tem;
  			}
  		}
  	}
  }
  

• 代码二：(轮流排所有小组，即第一组先排一个，然后排第二组的第一个… 然后排第一组的第二个，第二组的第二个…)（这样做可以省去一层循环）

• void ShellSort(int* a, int n) {
  	int gap = n;
  	while(gap > 1){
  		gap /= 2;
  		for (int i = 0; i < n - gap; i++) {
  			int end = i;
  			int tem = a[i + gap];
  			while (end >= 0) {
  				if (tem < a[end]) {
  					a[end + gap] = a[end];
  					end -= gap;
  				}
  				else {
  					break;
  				}
  			}
  			a[end + gap] = tem;
  		}
  	}
  }
  

选择排序

• 第一种：直接选择排序（每一次遍历一遍右边未处理过的元素，找出其中最小的一个，放在排好序的元素的后面，然后重复进行）。且有一个优化，每一次遍历的时候同时选出未排序元素里面的最小值和最大值(对于选择排序，无论最坏和最好的情况都是O（n^2）)

• void SelectSort(int* a, int n) {
  	int left = 0;
  	int right = n - 1;
  	while (left < right) {
  		int min = left, max = left;
  		for (int i = left+1; i <= right; i++) {
  			if (a[i] < a[min]) {
  				min = i;
  			}
  			if (a[i] > a[max]) {
  				max = i;
  			}
  		}
  		swap(&a[left], &a[min]);
  		if (left == max) {
  			max = min;
  		}
  		//如果left==max，那么在进行left和min的交换的时候，就会将最大值换到原本最小值的位置上，
  		//如果是这种情况，则必须进行修正，即将max=min，以确保max始终是最大值的下标
  		swap(&a[right], &a[max]);
  		left++;
  		right--;
  	}
  }
  

• 第二种：堆排序（本质也是一种选择排序）

• void HeapSort(int* a,int n) {
  	//for (int i = 0; i < n; i++) {
  		//AdjustUp(a, i);//模拟插入建堆，只不过是在自身上进行整个过程（向上调整）
  	//}
  
  	//建堆的第二种方式：（向下调整）
  	for (int i = (n - 2) / 2; i>=0; i--) {
  		AdjustDown(a, n, i);
  	}
  
  	for (int i = n - 1; i > 0; i--) {
  		Swap(&a[0], &a[i]);
  		AdjustDown(a, i, 0);//每一次将最大的数字与数组的最后一个数字进行交换，然后对第一个数字进行向下调整，在重复上述操作
  	}
  }
  
  

交换排序

• 第一种：冒泡排序 （每一次遍历从前向后依次两两比较，将大的数放在两个位置的后面那个位置，相当于每一次遍历都能将为排序数据里最大的那个数移动到最后边）

• void BubbleSort(int* a, int n) {
  	int flag = 0;
  	for (int j = 0; j < n-1; j++) {
  		for (int i = 1; i < n-j; i++) {//相当于控制的是两个数里后边那个数的范围
  			if (a[i - 1] > a[i]) {
  				swap(&a[i - 1], &a[i]);
  				flag = 1;
  			}
  		}
  		if (flag = 0) {
  			return;
  		}
  	}
  }
  

• 第二种：快速排序 选出一个基准值，然后将它放在它排好序后应该在的位置，

• • 第一种思路：(以左边为key在有序时效率会大大降低，所以应该随机选key)

  • void QuickSort(int* a, int left, int right) {
    	if (left >= right) {
    		return;
    	}
    	int  begin =  left;
    	int end = right;
        
    //这是随机数选key法
        int randi = left + (rand() % (right - left));
        swap(&a[left], &a[randi]);
        int k = left;
    //
        
    //这是三数取中选key法
        int GetMidNUmi(int* a, int left, int right) {
            int mid = (left + right) / 2;
            if (a[left] < a[mid]) {
                if (a[mid] < a[right]) {
                    return mid;
                }
                else if (a[left] > a[right]) {
                    return left;
                }
                else {
                    return right;
                }
            }else {
                if (a[mid] > a[right]) {
                    return mid;
                }
                else if (a[left] > a[right]) {
                    return right;
                }
                else {
                    return left;
                }
            }
    }
        int tem = GetMidNUmi(a, left, right);
        swap(&a[left], &a[tem]);
        int k = left;
    //
        
    	while (left < right) {
    		while (left < right && a[right] >= a[k]) {
    			right--;
    		}
    		while (left < right && a[left] <= a[k]) {
    			left++;
    		}
    		swap(&a[left], &a[right]);
    	}
    	swap(&a[left], &a[k]);
    	k = right;
    	QuickSort(a, begin, k - 1);
    	QuickSort(a, k+1, end);
    }
    

  • 第二种思路：（挖坑法）

  • void QuickSort(int* a, int left, int right) {
    
    	if (left >= right) {
    		return;
    	}
    
    	int  begin =  left;
    	int end = right;
    	int tem = GetMidNUmi(a, left, right);
    	swap(&a[left], &a[tem]);
        
    	int k = a[left];
    	int index = left;
        
    	while (left < right) {
    		while (left < right && a[right] >= k) {
    			right--;
    		}
    		a[index] = a[right];
    		index = right;
    		while (left < right && a[left] <= k) {
    			left++;
    		}
    		a[index] = a[left];
    		index = left;
    	}
    	a[index] = k;
        
    	QuickSort(a, begin, index - 1);
    	QuickSort(a, index +1, end);
    }
    

  • 第三种： 前后双指针法

  • void QuickSort(int* a, int left, int right) {
    	if (left >= right) {
    		return;
    	}
    	int tem = GetMidNUmi(a, left, right);
    	swap(&a[left], &a[tem]);
    	int k = a[left];
    	int prev = left;
    	int cur = left + 1;
    	while (cur <= right) {
    		if (a[cur] < k) {
    			swap(&a[++prev], &a[cur]);
    		}
    		cur++;
    	}
    	swap(&a[prev], &a[left]);
    	QuickSort(a, left, prev - 1);
    	QuickSort(a, prev + 1, right);
    }
    

• • ***对于快排的优化：***在递归到达一定层数之后，如果数据量小于一个限度的时候，使用插入排序而不是继续递归下去会更有优势（所以优化就是快排+插入排序）

  • void InsertSort(int* a, int n) {
    	for (int i = 1; i < n; i++) {
    		int end = i - 1;
    		int tem = a[end+1];
    		while (end >= 0) {
    			if (tem < a[end]) {
    				a[end + 1] = a[end];
    				end--;
    			}
    			else {
    				break;
    			}
    		}
    		a[end + 1] = tem;
    	}
    }
    
    void QuickSort(int* a, int left, int right) {
    	if ((right - left + 1) > 10) {
    		int tem = GetMidNUmi(a, left, right);
    		swap(&a[left], &a[tem]);
    		int k = a[left];
    		int prev = left;
    		int cur = left + 1;
    		while (cur <= right) {
    			if (a[cur] < k) {
    				swap(&a[++prev], &a[cur]);
    			}
    			cur++;
    		}
    		swap(&a[prev], &a[left]);
    		QuickSort(a, left, prev - 1);
    		QuickSort(a, prev + 1, right);
    	}
    	else {
    		InsertSort(a+left, right - left + 1);
    		return;
    	}
    }//相当于大规模的时候使用快排，小规模的时候使用插入
    

  • 快排的非递归形式：(在递归形式的快排里，其实本质上每一次递归都是存下了当前这一层所处理的区间下标)

  • int st[1000];
    int tail = 0;
    void QuickSort(int* a, int left, int right) {
    	st[tail++] = right;
    	st[tail++] = left;
    	while (tail != 0) {
    		int begin = st[--tail];
    		int end = st[--tail];
            
    		//排序一趟
    		int tem = GetMidNUmi(a, begin, end);
    		swap(&a[begin], &a[tem]);
    		int keyi = begin;
    		int prev = begin;
    		int cur = begin + 1;
    		while (cur <= end) {
    			if (a[cur] < a[keyi]) {
    				swap(&a[++prev], &a[cur]);
    			}
    			cur++;
    		}
    		swap(&a[prev], &a[keyi]);
    		keyi = prev;
    
    		if(keyi + 1 < end) {
    			st[tail++] = end;
    			st[tail++] = keyi+1;
    		}
    		if (begin < keyi - 1) {
    			st[tail++] = keyi-1;
    			st[tail++] = begin;
    		}
    	}
    }
    

归并排序

• ​
  对于归并排序，应该使用黑盒思想去理解，相信merge函数可以让左，右区间分别有序，在当前层只需要合并左右两个有序区间即可

• void _MergeSort(int* a, int left, int right, int* tem) {
  	if (left >= right) {
  		return;
  	}
  	int mid = (right + left) / 2;
  	_MergeSort(a, left, mid, tem);
  	_MergeSort(a, mid+1, right, tem);
  	int begin1 = left; int end1 = mid;
  	int begin2 = mid+1; int end2 = right;
  	int flag = left;
  	while (begin1 <= end1 && begin2 <= end2) {
  		if (a[begin1] < a[begin2]) {
  			tem[flag++] = a[begin1++];
  		}
  		else {
  			tem[flag++] = a[begin2++];
  		}
  	}
  	while (begin1 <= end1) {
  		tem[flag++] = a[begin1++];
  	}
  	while (begin2 <= end2) {
  		tem[flag++] = a[begin2++];
  	}
  	for (int i = left; i <= right; i++) {
  		a[i] = tem[i];
  	}
  }
  void MergeSort(int* a, int n) {
  	int* tem = (int*)malloc(sizeof(int) * n);
  	_MergeSort(a, 0, n - 1, tem);
  	free(tem);
  }
  

• 非递归的归并排序（不能使用栈，因为它相当与是一个后序遍历，而用栈模拟相当于是一个前序，所以应该使用循环直接改非递归）

• void MergeSort(int* a, int n) {
  	int* tem = (int*)malloc(sizeof(int) * n);
  	
  	int gap = 1;
  	while(gap<n){
  		for (int j = 0; j < n; j += 2*gap) {
  			int begin1 = j; int end1 = j + gap - 1;
  			int begin2 = j + gap; int end2 = j + 2 * gap - 1;
  
  			if (end1 >= n || begin2 >= n) {
  				break;
  			}
  			else if (end2>=n) {
  				end2 = n - 1;
  			}
  
  			int flag = j;
  			while (begin1 <= end1 && begin2 <= end2) {
  				if (a[begin1] < a[begin2]) {
  					tem[flag++] = a[begin1++];
  				}
  				else {
  					tem[flag++] = a[begin2++];
  				}
  			}
  			while (begin1 <= end1) {
  				tem[flag++] = a[begin1++];
  			}
  			while (begin2 <= end2) {
  				tem[flag++] = a[begin2++];
  			}
  			for (int i = j; i <= end2; i++) {
  				a[i] = tem[i];
  			}
  		}
  		
  		gap *= 2;
  	}
  	free(tem);
  }
  

计数排序

本质上就是一种哈希思想

void CountSort(int* a, int n) {
	int min = a[0];
	int max = a[0];
	for (int i = 1; i < n; i++) {
		if (a[i] > max) {
			max = a[i];
		}
		if (a[i] < min) {
			min = a[i];
		}
	}
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	memset(count, 0, sizeof(int) * range);
	for (int i = 0; i < n; i++) {
		count[a[i] - min]++;
	}
	int flag = 0;
	for (int i = 0; i < range; i++) {
		while (count[i]--) {
			a[flag++] = i + min;
		}
	}
	free(count);
}