汽车网站建设论坛,红色培训网站源码,做的系统怎么和网站对接,vps wordpress hostgator文章目录 1 二分查找2 冒泡排序3 堆排序4 插入排序5 快速排序6 选择排序7 希尔排序 1 二分查找
定义两个变量left和right#xff0c;分别表示数组的左边界和右边界#xff0c;初始值分别为0和len - 1#xff0c;其中len是数组的长度。计算数组的中间位置mid#xff0c;公式… 文章目录 1 二分查找2 冒泡排序3 堆排序4 插入排序5 快速排序6 选择排序7 希尔排序 1 二分查找
定义两个变量left和right分别表示数组的左边界和右边界初始值分别为0和len - 1其中len是数组的长度。计算数组的中间位置mid公式为(left right) / 2并判断数组中该位置的元素num[mid]是否等于目标值target。如果相等说明找到了目标值返回mid作为结果。如果不相等比较num[mid]和target的大小如果num[mid] target说明目标值在数组的右半部分因此将左边界更新为mid 1如果num[mid] target说明目标值在数组的左半部分因此将右边界更新为mid - 1。重复步骤2到4直到左边界大于右边界这时说明数组中不存在目标值返回-1作为结果。 二分查找算法的优点是查找速度快时间复杂度为 O ( l o g n ) O(logn) O(logn)其中n是数组的长度。缺点是要求数组必须是有序的并且对于动态变化的数组不适用。
int BinarySearch(int num[],int target,int len)
{int left 0, right len - 1;while(left right){int mid (left right) / 2;if(num[mid]target){return mid;}else if(num[mid] target){left mid 1;}else{right mid - 1;}}return -1;
}2 冒泡排序
定义一个变量i表示数组中未排序的部分的最后一个元素的位置初始值为length - 1其中length是数组的长度。从数组的第一个元素开始依次比较相邻的两个元素如果前一个元素num[j]大于后一个元素num[j1]则交换它们的位置这样可以将较大的元素向后移动。重复步骤2直到遍历到数组中未排序部分的最后一个元素这时可以确定该元素是数组中最大的元素并将其排在正确的位置。将变量i减一表示数组中未排序部分的长度减少了一个元素然后回到步骤2继续进行比较和交换。重复步骤2到4直到变量i小于等于1这时说明数组中所有的元素都已经排好序算法结束。 冒泡排序算法的优点是简单易懂不需要额外的空间。缺点是效率低时间复杂度为 O ( n 2 ) O(n^2) O(n2)其中n是数组的长度。
void BubbleSort(int num[],int length)
{for(int ilength-1;i1;i--){for(int j0;ji;j){if(num[j] num[j1]){int tmp num[j1];num[j1] num[j];num[j] tmp;}}}
}3 堆排序
定义一个函数MaxHeap它的作用是将一个数组中的一部分元素调整为一个大根堆即满足父节点的值大于等于子节点的值的二叉树。函数的参数有三个分别是num表示数组start表示调整的起始位置end表示调整的结束位置。在函数MaxHeap中定义两个变量dad和son分别表示当前要调整的父节点和子节点的位置初始值分别为start和start * 2 1因为数组下标从0开始所以左子节点是父节点乘以2再加1。判断子节点是否在调整范围内如果是则继续执行以下步骤如果不是则说明已经调整完毕返回。如果存在右子节点并且右子节点的值大于左子节点的值则将子节点更新为右子节点即选择较大的子节点。比较父节点和子节点的值如果父节点的值大于等于子节点的值则说明已经满足大根堆的性质返回如果不是则交换父节点和子节点的值并将父节点更新为原来的子节点子节点更新为原来父节点的左子节点即向下一层继续调整。重复步骤3到5直到调整完毕或者返回。定义一个函数HeapSort它的作用是对一个数组进行堆排序。函数的参数有两个分别是num表示数组len表示数组的长度。从数组中间位置开始依次对每个元素执行函数MaxHeap这样可以将整个数组调整为一个大根堆即第一个元素是最大的元素。从数组最后一个元素开始依次执行以下步骤 交换第一个元素和当前元素的值这样可以将最大的元素放在正确的位置。对除了当前元素之外的其他元素执行函数MaxHeap这样可以将剩余部分重新调整为一个大根堆即第一个元素是剩余部分最大的元素。 重复步骤9直到只剩下第一个元素这时说明数组中所有的元素都已经排好序算法结束。 堆排序算法的优点是效率高时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)其中n是数组的长度。缺点是需要额外的空间来存储堆结构并且对于稳定性要求高的场合不适用。
void MaxHeap(int num[],int start,int end)
{int dad start;int son dad * 2 1;while(son end){if((son1end) (num[son]num[son1])){son;}if(num[son]num[dad]){return;}else{int tmp num[dad];num[dad] num[son];num[son] tmp;dad son;son dad * 2 1;}}
}void HeapSort(int num[],int len)
{for(int ilen/2-1;i0;i--){MaxHeap(num,i,len-1);}for(int ilen-1;i0;i--){int tmp num[0];num[0] num[i];num[i] tmp;MaxHeap(num,0,i-1);}
}4 插入排序
定义一个变量i表示当前要插入的元素的位置初始值为1表示从数组的第二个元素开始。将当前要插入的元素num[i]保存在一个临时变量tmp中以免被覆盖。定义一个变量j表示已经排好序的部分的最后一个元素的位置初始值为i - 1。比较已经排好序的部分的最后一个元素num[j]和要插入的元素tmp的大小如果前者大于后者则将前者向后移动一位即将num[j]赋值给num[j1]并将j减一如果不是则说明找到了要插入的位置跳出循环。将要插入的元素tmp赋值给找到的位置即将tmp赋值给num[j1]。将变量i加一表示要插入下一个元素并回到步骤2继续进行比较和移动。重复步骤2到6直到变量i等于数组的长度这时说明数组中所有的元素都已经排好序算法结束。 插入排序算法的优点是简单易懂对于部分有序或者数据量较小的数组效率较高。缺点是效率低时间复杂度为 O ( n 2 ) O(n^2) O(n2)其中n是数组的长度。
void InsertSort(int num[],int length)
{for(int i1;ilength;i){int tmp num[i];int j i - 1;while((j0) (num[j]tmp)){num[j1] num[j];j--;}num[j1] tmp;}
}5 快速排序
定义一个函数QuickSort它的作用是对一个数组的一部分进行快速排序。函数的参数有三个分别是num表示数组start表示排序的起始位置end表示排序的结束位置。判断是否需要排序如果起始位置大于等于结束位置则说明已经排好序返回如果不是则继续执行以下步骤。定义两个变量i和j分别表示当前要划分的部分的左边界和右边界初始值分别为start和end。选择数组中第一个元素num[i]作为基准值并将其保存在一个临时变量basenum中以免被覆盖。从右边界开始向左寻找一个小于基准值的元素如果找到则将其赋值给左边界位置如果没有找到则将右边界减一继续寻找。从左边界开始向右寻找一个大于基准值的元素如果找到则将其赋值给右边界位置如果没有找到则将左边界加一继续寻找。重复步骤5和6直到左边界和右边界相遇或者交叉这时说明已经完成了一次划分并将基准值赋值给相遇或者交叉的位置。对基准值左边的部分递归地执行函数QuickSort对基准值右边的部分递归地执行函数QuickSort。重复步骤2到8直到所有的部分都排好序算法结束。 快速排序算法的优点是效率高时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)其中n是数组的长度。缺点是不稳定并且对于极端情况如数组已经有序或者逆序效率低。
void QuickSort(int num[],int start,int end)
{if(start end) return;int i start;int j end;int basenum num[i];while(ij){//从右往左找小值while((ij) (num[j]basenum)){j--;}if(ij){num[i] num[j];i;}//从左往右找大值while((ij) (num[i]basenum)){i;}if(ij){num[j] num[i];j--;}num[i] basenum;}QuickSort(num,start,i-1);QuickSort(num,i1,end);
}6 选择排序
定义一个变量i表示当前要选择的位置初始值为0表示从数组的第一个元素开始。定义一个变量min表示当前最小元素的位置初始值为i。从当前位置开始向后遍历数组中的每个元素如果发现有比当前最小元素更小的元素则将其位置赋值给min这样可以找到当前范围内最小的元素。交换当前位置和最小元素的值即将num[min]赋值给num[i]将num[i]赋值给num[min]这样可以将最小的元素放在正确的位置。将变量i加一表示要选择下一个位置并回到步骤2继续进行选择和交换。重复步骤2到5直到变量i等于数组的长度减一这时说明数组中所有的元素都已经排好序算法结束。 选择排序算法的优点是简单易懂不需要额外的空间。缺点是效率低时间复杂度为 O ( n 2 ) O(n^2) O(n2)其中n是数组的长度。
void SelectSort(int num[],int length)
{for(int i0;ilength-1;i){int min i;for(int ji;jlength;j){if(num[j]num[min]){min j;}}int tmp num[min];num[min] num[i];num[i] tmp;}
}7 希尔排序
定义一个变量gap表示当前要排序的元素的间隔初始值为数组的长度length。计算新的间隔公式为gap gap / 3 1这样可以逐渐减小间隔直到为1。对每个间隔进行以下步骤 定义一个变量i表示当前要排序的间隔的起始位置初始值为0。从当前位置开始向后遍历数组中的每个间隔内的元素如果发现有比前一个间隔内的元素更小的元素则将其保存在一个临时变量tmp中并执行以下步骤 定义一个变量k表示已经排好序的部分的最后一个间隔内的元素的位置初始值为当前位置减去间隔即k j - gap。比较已经排好序的部分的最后一个间隔内的元素num[k]和要插入的元素tmp的大小如果前者大于后者则将前者向后移动一个间隔即将num[k]赋值给num[kgap]并将k减去间隔继续比较如果不是则说明找到了要插入的位置跳出循环。将要插入的元素tmp赋值给找到的位置即将tmp赋值给num[kgap]。 将变量i加一表示要排序下一个间隔并回到步骤3.2继续进行遍历和插入。 重复步骤2和3直到变量gap等于1这时说明数组中所有的元素都已经排好序算法结束。 希尔排序算法的优点是效率高于简单插入排序时间复杂度为 O ( n 1.3 ) O(n^{1.3}) O(n1.3)其中n是数组的长度。缺点是不稳定并且对于不同的间隔选择效率有影响。
void ShellSort(int num[],int length)
{int gap length;do{gap gap / 3 1;for(int i0;igap;i){for(int jgapi;jlength;jgap){if(num[j] num[j-gap]){int tmp num[j];int k;for(kj-gap;(k0) (num[k]tmp);k-gap){num[kgap] num[k];}num[kgap] tmp;}}}} while(gap1);
}
