排序算法
2018-09-05 本文已影响0人
喝酸奶要舔盖__
计数排序
思想: 利用数组的索引,将对应的数组当做数组的索引,将所对应的元素赋给一个值,遍历这个数组取值
#include <stdio.h>
int main()
{
/*
* 计数排序:
* 从键盘输入5个 0~9之间的数字,排序之后输出
*
* 注意点: 计数排序只能用于有限的数字排序
* 在所有排序算法中,如果需要排序的数组是在有限范围内,并且不是很多的情况
* 计数排序的效率是最高的
*/
//1. 定义一个索引是0~9的数组
int arr[10] = {0};
int num = -1;
int len = sizeof(arr) / sizeof(arr[0]);
for(int i = 0; i < 5; i++){
printf("请输入数字\n");
scanf("%i", &num);
arr[num] += 1; //输入重复的数字,此处+1
}
//遍历数组
for(int i = 0; i < len; i++){
// 5 1 3 7 3 排序前
//arr[10] = {0,1,0,2,0,1,0,1,0,0}
// 0
// 1
// 0
// 2
// 0
for(int j = 0; j < arr[i]; j++){
printf("i = %i\n", i); // 1 3 3 5 7 排序后
}
}
return 0;
}
选择排序
思想: 从第一个数组中第一个元素开始,依次和下一个元素比较,这样一轮下来会产生一个最值在第一位,第二轮用索引为1的元素在依次和下面比较..
#include <stdio.h>
void printArray(int arr[], int len);
int main()
{
/*
* 选择排序
* 思想: 从第一个数组中第一个元素开始,依次和下一个元素比较,这样一轮下来会产生一个最值
* 在第一位,第二轮用索引为1的元素在依次和下面比较..
* 代码实现: 1.实现打印倒三角
2.实现输出需要比较的索引
3.判断条件交换位置
*
*/
int arr[5] = {3, 5, 4, 8, 7};
for(int i = 0; i < 4; i ++){
for(int j = i; j < 4; j++){
//printf("i=%i,j=%i\n", i, j+1); i 和 j+1代表索引
if(arr[i] > arr[j+1]){
int temp = arr[i];
arr[i] = arr[j+1];
arr[j+1] = temp;
}
}
}
printArray(arr, 5);
return 0;
}
void printArray(int arr[], int len){
for(int i = 0; i < len; i++){
printf("arr[%i] = %i\n", i, arr[i]);
}
}
- 选择排序封装
#include <stdio.h>
void selectSort(int arr[], int len);
void swapEle(int arr[], int i, int j);
void printArray(int arr[], int len);
int main()
{
/*
* 选择排序封装函数
*
*/
int arr[4] = {7,1,8,8};
int len = sizeof(arr) / sizeof(arr[1]);
selectSort(arr,len);
printArray(arr,len);
return 0;
}
//选择排序函数
void selectSort(int arr[], int len){
for(int i = 0; i < len -1; i++){
for(int j = i; j < len - 1; j++){
if(arr[i] > arr[j + 1]){
swapEle(arr, i, j+1);
}
}
}
}
//排序交换
/*
* 在看函数内部会不会修改实参的时候,只看函数的参数是什么类型
* 1. 如果是基本数据类型,实参就不会随形参更改
* 2. 如果是数组类型,实参就会随形参的更改而更改
*/
void swapEle(int arr[], int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void printArray(int arr[], int len){
for(int i = 0; i < len; i++){
printf("arr[%i] = %i\n", i, arr[i]);
}
}
冒泡排序
#include <stdio.h>
void printArray(int arr[], int len);
int main()
{
/*
* 冒泡排序
* 思想: 每相邻的两个元素两两比较,一轮结束会产生一个最值在最后一位
*
*/
int arr[4] = {3, 2, 1, 6};
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3-i; j++){
//printf("%i,%i\n", j, j+1);
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
printArray(arr, 4);
return 0;
}
void printArray(int arr[], int len){
for(int i = 0; i < len; i++){
printf("arr[%i] = %i\n", i, arr[i]);
}
}
- 冒泡排序封装
#include <stdio.h>
void swapEle(int arr[], int i, int j);
void printArray(int arr[], int len);
void bubbleSort(int arr[],int len);
int main()
{
/*
* 冒泡排序封装
*
*
*/
int arr[4] = {7,1,5,8};
int len = sizeof(arr) / sizeof(arr[1]);
bubbleSort(arr,len);
printArray(arr,len);
return 0;
}
void bubbleSort(int arr[],int len){
for(int i = 0; i < len -1; i++){
for(int j = 0; j < len -1-i; j++){
if(arr[j] > arr[j+1]){
swapEle(arr,j ,j+1);
}
}
}
}
void swapEle(int arr[], int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void printArray(int arr[], int len){
for(int i = 0; i < len; i++){
printf("arr[%i] = %i\n", i, arr[i]);
}
}
插入排序
#include <stdio.h>
void printArray(int arr[], int len);
int main()
{
/*
* 插入排序
* 每次都是用后一个元素和前面所有元素进行比较
* 一旦发现后一个元素小于前面的一个元素就让前面一个元素往后移动
* 或者一旦发现条件不满足就立刻插入到数组中
*/
int arr[4] = {3,9,4,2};
//1. 实现从第一个元素开始取出,和前面的元素依次比较
for(int i = 1; i < 4; i++){
//2. 取出用于和其他元素比较的元素
int temp = arr[i];
int j = i;
while(j > 0){
//判断取出这个元素是否小于前面那个元素
if(temp < arr[j-1]){
//把前面的元素往后挪一位
arr[j] = arr[j-1];
//如果当前元素不小于前面的元素直接结束循环
}else {
break;
}
j--;
}
arr[j] = temp;
}
printArray(arr,4);
return 0;
}
void printArray(int arr[], int len){
for(int i = 0; i < len; i++){
printf("arr[%i] = %i\n", i, arr[i]);
}
}
希尔排序
#include <stdio.h>
void printArray(int arr[], int len);
int main()
{
/*
* 希尔排序:
* 思想 : 用当前数组长度/2计算出步长,取出当前步长对应索引的元素和当前索引-步长对应的元素
* 比较满足条件就交换,下一步就是把步长+1取出当前对应索引的元素,再取出当前元素索引-步长的元素
* 比较...
*
*
*/
int arr[6] = {3,8,4,1,2,6};
int len = sizeof(arr) / sizeof(arr[1]);
//1. 计算步长
int gap = len /2;
do{
//2. 取出当前gap对应的元素和当前元素索引减步长对应的元素比较
for(int i = gap; i < len; i++){
//3. 定义变量用于保存当前元素索引减步长对应的元素
int j = i; //当前索引
while ((j - gap) >= 0) {
if(arr[j] < arr[j-gap]){
//满足条件就交换位置
int temp = arr[j];
arr[j] = arr[j - gap];
arr[j-gap] = temp;
}else {
break;
}
j--;
}
}
gap = gap / 2;
}while (gap >=1);
printArray(arr, len);
return 0;
}
void printArray(int arr[], int len){
for(int i = 0; i < len; i++){
printf("arr[%i] = %i\n", i, arr[i]);
}
}
折半查询
注意点: 数组必须是有序的,才能使用该方法
#include <stdio.h>
int main()
{
/*
* 折半查询:
* 注意点: 数组必须是有序的
* 思想: 就是三个变量 min max mid = (min + max)/2
* 需求: 根据指定的值,在数组中找到对应该元素的索引
*
*/
int arr[6] = {1,3,5,6,8,9};
int key = 3;
int len = sizeof(arr) / sizeof(arr[1]);
//1. 定义三个变量
int min = 0;
int max = len -1;
int mid = (min + max) / 2;
//2. 判断条件
while(max >= min){
if(arr[mid] < key){
min = mid +1;
mid = (min + max) / 2;
}else if(arr[mid] > key){
max = mid -1;
mid = (min + max) / 2;
}else {
printf("%i\n", mid);
return;
}
}
//没有查询到结果
printf("没有查询到结果");
return 0;
}
