首页 > 代码库 > 第四篇、快速、冒泡、选择、插入排序
第四篇、快速、冒泡、选择、插入排序
1.快速排序
实现：
1.取中间一个数作为支点
2.分别在支点的左右两边进行查找，如果左边查找到比支点大，右边查找到比支点小，就交换位置，如此循环，比支点小的数就排在了左边，比支点大的就排在右边
3.左右两边再用递归排序，就可以完成排序操作
/***@brief 快速排序*@params arr 数组 left 起始位置 right总点位置*/void quickSort(int arr[],int left,int right){ int i = left; int j = right; int pivot = arr[(left + right) / 2]; // 支点 while(i <= j) { while(arr[i] < pivot) { i++; } while(arr[j] > pivot) { j--; } if(i<=j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } // 递归 if(left < j) { quickSort(arr,left,j); } if(i < right) { quickSort(arr,i,right); }}
2.冒泡排序
原理：如果当前这个数比下一个数大，则交换位置，经过一次之后最大的数就排到了数组的末尾，以此类推
void bubble(inti arr[],int n){ int i ; int temp; for(i=0;i<n-1;i++) { if(arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } }}void bubbleSort(int arr[],int n){ int i; for(i = n; i>=1; i--) { bubble(arr,i); }}
3.选择排序
思路：
1.首先在数组中找到最大值并记录其下标
2.然后最大值与数组下标为n-1的交换。
int findMaxPos(int arr[],int n){ int i; int max = arr[0]; int pos = 0; for(int i = 0; i<n; i++) { if(arr[i] > max) { pos = i; max = arr[i]; } } return pos;}void selectSort(int arr[],int n){ while(n > 1) { int pos = findMaxPos(arr,n); int temp = arr[pos]; arr[pos] = arr[n - 1]; arr[n - 1] = temp; n--; }}
4.插入排序
思路：
1.首要条件：两个数及以上
2.取到当前要插入的元素，以前面一个比较，如果小于前面，则需要把前面的大数移位，直到不满足小于的条件，插入相应的位置
void insert(int arr[],int n){ int key = arr[n]; int i = n; while(arr[i - 1] > key) { arr[i] = arr[i - 1]; i--; if(i == 0) { break; } } arr[i] = key;}void insertionSort(int arr[],int n){ int i; for(i=1; i< n; i++) { insert(arr,i); }}
第四篇、快速、冒泡、选择、插入排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。