C++实现各种排序算法

绝地灬酷狼 2022-09-07 01:23 192阅读 0赞

1.  插入排序  
    直接插入排序、折半插入排序、希尔排序
2.  交换排序  
    冒泡排序、快速排序
3.  选择排序  
    简单选择排序、堆排序

#include<bits/stdc++.h>
    using namespace std;
    
    //直接插入排序 
    void st_insert_sort(vector<int>& nums) { 
    	int n = nums.size();
    	for(int i = 1; i < n; i++) { 
    		int cur = nums[i];
    		int j = i - 1;
    		while(cur < nums[j] && j >= 0) { 
    			nums[j + 1] = nums[j];
    			j--;
    		}
    		j != -1 ? nums[j + 1] = cur : nums[0] = cur;
    	}
    }
    
    //二分插入排序 
    void bs_insert_sort(vector<int>& nums) { 
    	int n = nums.size();
    	for(int i = 1; i < n; i++) { 
    		int cur = nums[i];  //待插入元素
    		int low = 0, high = i - 1;
    		while(low <= high) { 
    			int mid = low + (high - low) / 2;
    			if(nums[mid] <= cur) { 
    				low = mid + 1;
    			} else { 
    				high = mid - 1;
    			}
    		}
    		//插入位置为high + 1
    		for(int j = i - 1; j >= high + 1; j--) { 
    			nums[j + 1] = nums[j];
    		} 
    		nums[high + 1] = cur;
    	}
    }
    
    //希尔排序
    void shellpass(vector<int>& nums, int step) { 
    	int n = nums.size();
    	for(int i = step; i < n; i++) {   //从每组的第二个记录开始进行插入排序 
    		int cur = nums[i];
    		int j = i - step;
    		while(j >= 0 && cur < nums[j]) { 
    			nums[j + step] = nums[j];
    			j -= step;
    		}
    		nums[j + step] = cur;
    	} 
    }
    
    void shellsort(vector<int>& nums) { 
    	vector<int> d = { 5, 3, 1};
    	for(int x : d) { 
    		shellpass(nums, x);
    	}
    }
    
    //冒泡 
    void bubble_sort(vector<int>& nums) { 
    	int n = nums.size();
    	bool flag = false;
    	for(int i = 0; i < n - 1; i++) { 
    		for(int j = 0; j < n - 1 - i; j++) { 
    			if(nums[j] > nums[j + 1]) { 
    				flag = true;
    				int t = nums[j];
    				nums[j] = nums[j + 1];
    				nums[j + 1] = t;
    			}
    		}
    		if(flag) { 
    			flag = false;
    			continue;
    		}else { 
    			return;
    		}
    	}
    }
    
    //快排 
    int partition(vector<int>& nums, int low, int high) { 
    	int cur = nums[low]; //基准
    	while(low < high) { 
    		while(high > low && nums[high] >= cur){ 
    			high--;
    		}
    		nums[low] = nums[high];
    		while(low < high && nums[low] <= cur) { 
    			low++;
    		}
    		nums[high] = nums[low];
    	}
    	nums[low] = cur;
    	return low;
    }
    
    void q_sort(vector<int>& nums, int low, int high) { 
    	if(low < high) { 
    		int loc = partition(nums, low, high);
    		q_sort(nums, low, loc - 1);
    		q_sort(nums, loc + 1, high);
    	}
    }
    
    //简单选择排序
    void simple_selectsort(vector<int>& nums) { 
    	int n = nums.size();
    	for(int i = 0; i < n - 1; i++) { 
    		int _min = INT_MAX, k = i + 1;
    		for(int j = i; j < n; j++) { 
    			if(nums[j] < _min) { 
    				_min = nums[j];
    				k = j;
    			}
    		}
    		//将nums[i]与nums[k]交换 
    		int t = nums[i];
    		nums[i] = nums[k];
    		nums[k] = t;
    	}
    }
    
    //堆排序
    void swap(vector<int>& nums, int i, int j) { 
    	int t = nums[i];
    	nums[i] = nums[j];
    	nums[j] = t;
    }
    
    void adjust(vector<int>& arr, int x, int n) { 
    	//调整序号为x的元素
    	int temp = arr[x];
    	//2x+1和2x+2分别是x的左右孩子
    	for(int k = 2 * x + 1; k < n; k = 2 * k + 1) {   //调整后指向其左孩子 
    		if(k + 1 < n && arr[k] < arr[k + 1]) { 
    			k++;  //x的右孩子比左孩子更大 
    		}
    		if(temp < arr[k]) { 
    			arr[x] = arr[k]; //将x的左右孩子中的较大值赋给x
    			x = k; 
    		}else { 
    			break;
    		}
    	} 
    	arr[x] = temp;  //此时要将待排序的点插入 
    }
    
    void heapSort(vector<int>& arr) { 
    	int n = arr.size();
    	//先将初始序列建成大根堆, 最后一个非叶子结点的序号为n/2-1(堆顶序号为0) 
    	for(int i = n / 2 - 1; i >= 0; i--) { 
    		adjust(arr, i, n); //调整第i个结点使arr[0...n - 1]成为大根堆 
    	} 
    	//堆排序
    	for(int i = n - 1; i > 0; i--) { 
    		//将末尾元素与堆顶交换，然后再调整 
    		int t = arr[0];
    		arr[0] = arr[i];
    		arr[i] = t;
    		adjust(arr, 0, i);  //调整堆顶使arr[0...i - 1]再次成为大根堆
    	} 
    }
    
     
    int main() { 
    	vector<int> nums = { 26, 18, 20, 18, 38, 30, 20, 23, 31, 29};
    	int n = nums.size();
    	heapSort(nums);
    	for(int x : nums) { 
    		cout << x << " ";
    	}
    	return 0;
    }