数据结构排序算法 + 查找算法

一、概念

程序=数据结构+算法

1.算法的特性和要求

特性：

确定性（每次运行相同的输入都是同样的结果）、有穷性、输入、输出、可行性

设计要求：

正确性、高效率、低存储、健壮性、可读性

2.时间复杂度

3.常见排序算法的时间复杂度

冒泡排序：O(n^2)

选择排序：O(n^2)

快速排序：O(nlog2n）

直接插入排序:最坏情况O(n^2),最好情况O(n)

二、排序代码

1.冒泡排序

int len=sizeof(arr)/sizeof(arr[0]);
for(int i=1;i<len;i++)
{
    for(int j=0;j<len-i;j++)
    {
        if(arr[j]>arr[j+1])
        {
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;        
        }    
    }
}

2.选择排序

已知min_index,长度len
for(int i=1;i<len;i++)
{
    min_index = i-1;  //假定最小值是待排序序列中的第一个元素
    for(int j=i;j<len;j++)
    {
        if(arr[min_index]>arr[j])
        {
            min_index = j;        
        }    
    }
    temp = arr[min_index];
    arr[min_index] = arr[i-1];
    arr[i-1] = temp;
}

3.快速排序

#include <stdio.h>
#include <string.h>
//定义一次快排的函数，返回最后基准的位置
int one_sort(int *arr,int low,int high){
	int base=arr[low];
	//只要high大于low说明没排好序
	while(low<high){
		while(low<high && arr[high]>=base){//当high>low并且high位置元素大于基准时high前移
			high--;
		}
		arr[low]=arr[high];//用high下标的元素覆盖掉low下标的元素

		//当high>low并且low下标元素小于base时，low后移
		while(low<high && arr[low]<=base){
			low++;
		}
		arr[high]=arr[low];
	}
	arr[low]=base;
	return low;
}
void sort(int *arr,int low,int high){
	//传过来的low<high说明无序
	if(low<high){
		int ret =one_sort(arr,low,high);//接收一次快排后中间位置（基准）
		sort(arr,low,ret-1);
		sort(arr,ret+1,high);
	}
}
int main(int argc, const char *argv[])
{
	int arr[]={12,90,78,23,1,10,56,11};
	int len=sizeof(arr)/sizeof(int);
	sort(arr,0,len-1);
	for(int i=0;i<len;i++){
		printf("%d ",arr[i]);
	}
	putchar(10);
	return 0;
}

4.直接插入排序

#include <stdio.h>
#include <string.h>

void insert_sort(int *arr,int len){
	int i,j,temp;
	//循环插入元素进入待排序序列中
	for(i=1;i<len;i++){  //从第二个元素开始
		temp=arr[i];  //把要插入的元素保存一下
		for(j=i;j>0 && temp<arr[j-1];j--){   //用前面的每一个元素与待插入的元素比较
			arr[j]=arr[j-1]; //把前面的元素后移
		}
		//退出了内层循环，说明找到了要插入的位置、

		arr[j]=temp;  //把要插入的元素插入
	}
}
int main(int argc, const char *argv[])
{
	int arr[]={12,90,78,23,1,10};
	int len=sizeof(arr)/sizeof(arr[1]);
	insert_sort(arr,len);
	for(int i=0;i<len;i++){
		printf("%d ",arr[i]);
	}
	putchar(10);
	return 0;
}

 三、查找算法代码

1.折半查找

折半查找的前提：对有序序列进行查找

#include <stdio.h>
#include <string.h>

int half_search(int *arr,int low,int high,int key){
	//如果传过来的最大值下标大于最小值的下标
	while(low<=high){
		//找中间值
		int mid=(low+high)/2;//得到中间值的下标;
		if(arr[mid]==key){
			printf("查找成功\n");
			return mid;
		}
		if(key<arr[mid])
			high=mid-1;
		else if(key>arr[mid])
			low=mid+1;
			
	}
return 0;
}
int main(int argc, const char *argv[])
{
	int arr[]={11,12,13,23,59,78,100};
	int len=sizeof(arr)/sizeof(arr[1]);
	printf("%d\n",half_search(arr,0,len-1,99));
	return 0;
}

2.哈希排序

哈希表的构造方法：

除留余数法：关键字对指定数据取模后，得到的就是关键字在哈希表中的下标

取模的数：关键字个数除3/4 ===>关键字个数*4/3 取最大质数

hash.c

#include "hash.h"

//创建结点的函数
node_p create_node(int data)
{
	node_p new=(node_p)malloc(sizeof(node));
	if(new==NULL){
		printf("申请失败\n");
		return NULL;
	}
	new->data=data;
	new->next=NULL;
	return new;
}
//存储函数
void save_hash(node_p hash[],int key)
{
	int base=key%MAX;//除留余数法
	node_p new=create_node(key);//申请新节点，把新节点存入哈希表
	//把新节点存入哈希表
	new->next=hash[base];
	hash[base]=new; //让结构体指针指向新节点
	//hash[base]中存的是第一个元素的地址
}
//打印函数
void show_hash(node_p hash[]){
	//循环结构体指针数组，即hash表
	for(int i=0;i<MAX;i++){
		//循环链表
		node_p p=hash[i];
		while(p!=NULL){
			printf("%d->",p->data);
			p=p->next;
		}
		printf("^\n");
	}
}
//查找
void search_hash(node_p hash[],int key){
	/*	//法一:
	//直接取到关键对13取模的结果
	int base=key%MAX;
	int i=1;
	//准备遍历整条链表
	node_p p=hash[base];
	//如果找到的关键字不符并且节点存在
	//	while(p->data!=NULL && p!=NULL){
	while(p!=NULL){
	if(p->data==key){
	printf("查找成功,数据在哈希表的%d位置\n",i);	
	break;
	}
	i++;
	p=p->next;
	}
	if(p==NULL)
	printf("查找失败\n");
	}
	*/
	//法二：
	int i;
	for(i=0;i<MAX;i++){
		node_p p=hash[i];
		while(p!=NULL){
			if(p->data==key){
				printf("查找成功\n");
				return;
			}
			p=p->next;
		}
	}
	if(i==MAX)
		printf("查找失败\n");
}

hash.h

#ifndef __HASH_H__
#define __HASH_H__
#include <stdio.h>
#include <stdlib.h>
#define MAX 13
typedef struct node{
	int data;
	struct node *next;
}node,*node_p;
//创建结点的函数
node_p create_node(int data);
//存储函数
void save_hash(node_p hash[],int key);
//打印函数
void show_hash(node_p hash[]);
//查找
void search_hash(node_p hash[],int key);

#endif

main.c

#include "hash.h"
int main(){
	int arr[]={25,51,8,22,26,67,11,16,54,41};
	int len=sizeof(arr)/sizeof(arr[1]);

	//申请一个结构体指针，里面存的是地址
	node_p hash[13]={0};//初始时指针都指向NULL
	for(int i=0;i<len;i++){
		save_hash(hash,arr[i]);
	}
	//show_hash(hash);
	search_hash(hash,11);
}