|
排序难点:算法多,容易混淆 1.直接(简单)插入排序:扑克牌
特点:越有序越快,完全有序O(n),非常重要,这个是希尔排序的基础
2.希尔(shell)排序 分组后利用直接插入排序 3.冒泡排序： 两两比较，大的往后走
* 4.快速排序： 算法：1.从后往前找比基准小的数字，找到往前挪
2.从前往后找比基准大的数字，找到往后挪 3.重复1.2
缺点：1.越有序，越慢
2.空间复杂度大，不稳定
5.选择排序： 每次都从待排序中选出最小的一个和待排序的第一个进行数据交换
6.堆排序： 算法：1.从最后一颗子树开始，从后往前调整
2.每次调整大数据排序，从上往下调整
3.调整为大根堆
大根堆：在二叉树中所有的父都大于子
小根堆：在二叉树中所有的父都小于子
度：就是节点的分支
叶子节点：度为0
兄弟：同一个双亲的孩子之前被称为兄弟
深度：就是树的层高
7.归并排序
1.将两段有序的数据合并成为一段有序的数据，直到所有的数据都有序
2.把两段有序的归并成为一段有序的，也称为2路有序
8.基数排序（桶排序）
局限性：不能处理负数
9.第‘9’个排序
链表排序
1.单链表存放数据我们用什么排序？（冒泡，选择）
2.双向链表存放数据我们用什么排序？（快排（STL自带的list为双向链表））
#include
#include
#include
#include"listqueue.h"
//直接(简单)插入排序
//void InsertSort(int* arr, int len)//O(n^2),最好的情况,O(1),稳定
//{
// int tmp;//存放当前处理的数字
// int j;
// for (int i = 1; i < len; i++)//从第二个数字开始
// {//1 2 3 4 5
// tmp = arr[i];
// for (j = i - 1; j >= 0; j--)//从后往前找第一个比tmp小的数字
// {
// if (arr[j] > tmp)//arr[j]需要后移
// arr[j + 1] = arr[j];
// else
// break;
// }
// arr[j + 1] = tmp;
// }
//}
//gap:分组数
//void Shell(int* arr, int len, int gap)
//{
// int tmp;//保存当前需要处理的值
// int j;
// for (int i = gap; i < len; i++)//从"第二个"元素开始
// {
// tmp = arr[i];
// for (j = i - gap; j >= 0; j -= gap)
// {
// if (arr[j] > tmp)
// arr[j + gap] = arr[j];
// else
// break;
// }
// arr[j + gap] = tmp;
// }
//}
//希尔排序
//void ShellSort(int* arr, int len)//时间复杂度：O(n^1.3~n^1.5),空间复杂度O(1),不稳定
//{
// int d[] = { 5,3,1 };//分组组数,注意最后一定是1.缩小增量
// for (int i = 0; i < sizeof(d) / sizeof(d[0]); i++)
// {
// Shell(arr, len, d[i]);
// }
//}
/*
void InsertSort(int* arr, int len)//O(n^2),完全有序O(n^2)这个程序写的有问题
{
int tmp;
int i;
int j;
for (i = 1; i < len; i++)//从第二个数字开始处理
{
tmp = arr[i];//需要处理的值
for (j = 0; j < i; j++)//找合适的位置,太慢
{
if (arr[j] > tmp)
break;
}//1 2 3 4 5
//把后面的数据往后移动
for (int k = i - 1; k >= j; k--)
{
arr[k + 1] = arr[k];
}
//插入新数据
arr[j] = tmp;
}
}
*/
//希尔排序（时间复杂度：O(n^1.3~n^1.5),空间复杂度O(1),不稳定）
//void Shell(int* arr, int len, int gap)
//{
// int tmp;int j;
// for (int i = gap; i < len; i ++)
// {
// tmp = arr[i];
// for ( j= i - gap; j >= 0; j -= gap)
// {
// if (arr[j] > tmp)
// {
// arr[j+gap] = arr[j];
// }
// else
// break;
// }
// arr[j+gap] = tmp;
// }
//}
//void ShellSort(int* arr, int len)
//{
// int d[] = { 5,3,1 };
// for (int i = 0; i < sizeof(d) / sizeof(d[0]); i++)
// {
// Shell(arr, len, i);
// }
//}
//冒泡排序( O(n^2),O(1),稳定)
//void Bubbler(int* arr, int len)
//{
// int temp;
// for (int i= 0; i < len-1; i++)
// {
// for (int j = 0; j + 1 < len - i; j++)
// {
// if (arr[j] > arr[j+1])
// {
// temp = arr[j];
// arr[j] = arr[j+1];
// arr[j+1] = temp;
// }
// }
// }
//}
//快速排序,O(nlogn),O(logn),不稳定
//int Partition(int* arr, int low, int high)//一次划分O(n),O(1)
//{
// int tmp = arr[low];//基准
// while (lowtmp)
// {
// high--;
// }
// if(low arr[j])
// {
// minlndex = j;
// }
// }
// //最小值和待排序的第一个值交换
// if (minlndex != i)
// {
// tmp = arr[minlndex];
// arr[minlndex] = arr[i];
// arr[i] = tmp;
// }
//
// }
//}
//堆排序
//父-->子：i-->2*i+1,2*i+2
//子-->父:i-->(i-1)/2
//void HeapAdjust(int* arr, int start, int end)
//{
// int tmp = arr[start];
// for (int i = 2 * start + 1; i <= end; i = 2*i+1)
// {
// if (i < end && arr[i] < arr[i + 1])//有右孩子，并且左孩子的值小于右孩子
// {
// i++;
// }//i一定是左右孩子的最大值
// if (arr[i] > tmp)
// {
// arr[start] = arr[i];
// start = i;
// }
// else
// {
// break;
// }
// }
// arr[start] = tmp;
//}
//
//void HeapSort(int* arr, int len)
//{
// //第一次建立大根堆，从后往前，多次调整
// int i;
// for (i = (len - 1 - 1) / 2; i >= 0; i--)
// {
// HeapAdjust(arr, i, len - 1);
// }
// //每次将根和待排序的最后一个做交换，然后再做调整
// int tmp;
// for (i = 0; i < len; i++)
// {
// tmp = arr[0];
// arr[0] = arr[len - 1 - i];
// arr[len - 1 - i] = tmp;
//
// HeapAdjust(arr, 0, len - 1 - i-1);
// }
//
//}
//归并有序O(nlogn),O(n),稳定
// 一次归并 O（n）
//void Merge(int* arr, int len, int gap)
//{
// int low1 = 0;//第一段起始下标，
// int high1 = low1 + gap-1;//第一段归并段的结束下标
// int low2 = high1 + 1;//第二个归并段的起始下标
// int high2 = low2 + gap-1
1.队列函数实现名命为listqueue.cpp
//桶排序需要用到队列
//这是队列的函数实现
#include
#include
#include
#include"listqueue.h"
//队列初始化
void InitQueue(LinkQueue* pq)
{
assert(pq != NULL);
if (pq == NULL)
return;
pq->front = NULL;
pq->rear=NULL;
}
//入队
bool Push(LinkQueue* pq, ElemType val)
{
QNode* p = (QNode*)malloc(sizeof(QNode));
assert(p != NULL);
if (p == NULL)
return false;
p->data = val;
p->next = NULL;
if (!IsEmpty(pq))
{
pq->rear->next = p;
pq->rear = p;
}
else
{
pq->rear = p;
pq->front = p;
}
return true;
}
//判空
bool IsEmpty(LinkQueue* pq)
{
return pq->front == NULL;//队头都没有元素
}
//获取队头元素,但不删除
bool GetHead(LinkQueue* pq, ElemType* rtval)
{
assert(pq != NULL);
if (pq == NULL)
return false;
*rtval = pq->front->data;
return true;
}
//出队,获取队头元素,且删除
bool DeQueue(LinkQueue* pq, ElemType* rtval)
{
assert(pq != NULL);
if (pq == NULL)
return false;
*rtval = pq->front->data;
QNode* p = (QNode*)malloc(sizeof(QNode));
p = pq->front;
pq->front = p->next;
free(p);
if (pq->front == NULL)
pq->rear == NULL;
return true;
}
//销毁
void Destroy(LinkQueue* pq)
{
QNode* p ;
while (pq->front!=NULL)
{
p = pq->front;
pq->front = p->next;
free(p);
}
pq->rear == NULL;
}
2.对列头文件名命为"listqueue.h"
//这是队列的头文件
#pragma once
typedef int ElemType;
typedef struct QNode
{
ElemType data;
struct QNode* next;
}QNode ,*QueuePtr;
typedef struct
{
QNode* front;//队头指针
QNode* rear;//队尾指针
}LinkQueue;//头结点的定义
//队列初始化
void InitQueue(LinkQueue* pq);
//入队
bool Push(LinkQueue* pq, ElemType val);
//判空
bool IsEmpty(LinkQueue* pq);
//获取队头元素,但不删除
bool GetHead(LinkQueue* pq, ElemType* rtval);
//出队,获取队头元素,且删除
bool DeQueue(LinkQueue* ps, ElemType* rtval);
//销毁
void Destroy(LinkQueue* ps);
2
（编辑：应用网_扬州站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
浙公网安备 33038102330458号