各大网站,wordpress 管理系统,合肥网站制作方案,西安官网seo方法一、数组: 所谓数组#xff0c;是有序的元素序列。 [1] 若将有限个类型相同的变量的集合命名#xff0c;那么这个名称为数组名。组成数组的各个变量称为数组的分量#xff0c;也称为数组的元素#xff0c;有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。…一、数组: 所谓数组是有序的元素序列。 [1] 若将有限个类型相同的变量的集合命名那么这个名称为数组名。组成数组的各个变量称为数组的分量也称为数组的元素有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中为了处理方便 把具有相同类型的若干元素按无序的形式组织起来的一种形式。 [1] 这些无序排列的同类数据元素的集合称为数组。 数组是用于存储多个相同类型数据的集合。 数组 (分类)一维、二维矩阵、三维数组 Array (定义)同类数据元素的集合 数组说明的一般形式为类型说明符 数组名 [常量表达式]…… 其中类型说明符是任一种基本数据类型或构造数据类型。数组名是用户定义的数组标识符。方括号中的常量表达式表示数据元素的个数也称为数组的长度。 数组就是一次性定义相同数据类型的一组变量数组定义。 举例 int a[10]; 说明整型数组a有10个元素。若要表示第10个元素则使用a[9]。第一个则是a[0]。 float b[10],c[20]; 说明实型数组b有10个元素实型数组c有20个元素。 char ch[20]; 说明字符数组ch有20个元素。
数组的特点: 1.数组是相同数据类型的元素的集合。 2.数组中的各元素的存储是有先后顺序的它们在内存中按照这个先后顺序连续存放在一起。 3.数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如a[0]表示名字为a的数组中的第一个元素a[1]代表 数组a的第二个元素以此类推。 对于VB的数组表示数组元素时应注意 1.下标要紧跟在数组名后而且用圆括号括起来不能用其他括号。 2.下标可以是常量变量或表达式但其值必须是整数如果是小数将四舍五入为整数)。 3.下标必须为一段连续的整数其最小值成为下界其最大值成为上界。不加说明时下界值默认为1。 数组中的元素与结构或类中的字段的区别: 数组中的所有元素都具有相同类型这一点和结构或类中的字段不同它们可以是不同类型。数组中的元素存储在一个连续性的内存块中并通过索引来访问这一点也和结构和类中的字段不同它们通过名称来访问。 类型:数组元素并非只能是基元数据类型还可以是结构、枚举或类。
数组的结构形式
栈内存
在方法中定义的一些基本类型的变量和对象的引用变量都在方法的栈内存中分配当在一段代码中定义一个变量时java就在栈内存中为这个变量分配内存空间当超出变量的作用域后java会自动释放掉为该变量所分配的内存空间。 堆内存
堆内存用来存放由new运算符创建的对象和数组在堆中分配的内存由java虚拟机的自动垃圾回收器来管理。在堆中创建了一个数组或对象后同时还在栈内存中定义一个特殊的变量。让栈内存中的这个变量的取值等于数组或者对象在堆内存中的首地址栈中的这个变量就成了数组或对象的引用变量引用变量实际上保存的是数组或对象在堆内存中的地址也称为对象的句柄以后就可以在程序中使用栈的引用变量来访问堆中的数组或对象。 [5] 与结构或类中的字段的区别
数组中的所有元素都具有相同类型(这一点和结构或类中的字段不同它们可以是不同类型)。数组中的元素存储在一个连续性的内存块中并通过索引来访问(这一点也和结构和类中的字段不同它们通过名称来访问)。
Array函数
array() 创建数组。
array_change_key_case() 返回其键均为大写或小写的数组。
array_chunk() 把一个数组分割为新的数组块。
array_column() 返回输入数组中某个单一列的值。
array_combine() 通过合并两个数组一个为键名数组一个为键值数组来创建一个新数组。
array_count_values() 用于统计数组中所有值出现的次数。
array_diff() 比较数组返回两个数组的差集只比较键值。
array_diff_assoc() 比较数组返回两个数组的差集比较键名和键值。
array_diff_key() 比较数组返回两个数组的差集只比较键名。
array_diff_uassoc() 比较数组返回两个数组的差集比较键名和键值使用用户自定义的键名 比较函数。
array_diff_ukey() 比较数组返回两个数组的差集只比较键名使用用户自定义的键名比较 函数。
array_fill() 用给定的键值填充数组。
array_fill_keys() 用给定的指定键名的键值填充数组。
array_filter() 用回调函数过滤数组中的元素。
array_flip() 反转/交换数组中的键名和对应关联的键值。
array_intersect() 比较数组返回两个数组的交集只比较键值。
array_intersect_assoc() 比较数组返回两个数组的交集比较键名和键值。
array_intersect_key() 比较数组返回两个数组的交集只比较键名。
array_intersect_uassoc() 比较数组返回两个数组的交集比较键名和键值使用用户自定义的键名 比较函数。
array_intersect_ukey() 比较数组返回两个数组的交集只比较键名使用用户自定义的键名比较 函数。
array_key_exists() 检查指定的键名是否存在于数组中。
array_keys() 返回数组中所有的键名。
array_map() 将用户自定义函数作用到给定数组的每个值上返回新的值。
array_merge() 把一个或多个数组合并为一个数组。
array_merge_recursive() 递归地把一个或多个数组合并为一个数组。
二、算法
首先声明一下本文只对十种排序算法做简单总结并参照一些资料给出自己的代码实现并没有对某种算法理论讲解更详细的
了解可以参考以下资料本人参考
1、《data structure and algorithm analysis in c 》
2、《大话数据结构》
3、http://blog.csdn.net/morewindows/article/details/7961256
4、http://www.cs.usfca.edu/~galles/visualization/Algorithms.html
一、冒泡排序
基本思想是:两两比较相邻记录的关键字,如果反序则交换
冒泡排序时间复杂度最好的情况为O(n),最坏的情况是O(n^2) 改进思路1设置标志位明显如果有一趟没有发生交换flag false)说明排序已经完成
改进思路2记录一轮下来标记的最后位置下次从头部遍历到这个位置就Ok
二、直接插入排序
将一个记录插入到已经排好序的有序表中, 从而得到一个新的,记录数增1的有序表
时间复杂度也为O(n^2), 比冒泡法和选择排序的性能要更好一些
三、简单选择排序
通过n-i次关键字之间的比较,从n-i1 个记录中选择关键字最小的记录,并和第i(1in)个记录交换之 尽管与冒泡排序同为O(n^2),但简单选择排序的性能要略优于冒泡排序
四、希尔排序
先将整个待排元素序列分割成若干子序列由相隔某个“增量”的元素组成的分别进行直接插入排序然后依次缩减增量再进行排
序待整个序列中的元素基本有序增量足够小时再对全体元素进行一次直接插入排序增量为1。其时间复杂度为O(n^3/2),要好于直接
插入排序的O(n^2)
五、归并排序
假设初始序列含有n个记录,则可以看成n个有序的子序列,每个子序列的长度为1,然后两两归并,得到(不小于n/2的最小整数)个长度为2
或1的有序子序列,再两两归并,...如此重复,直至得到一个长度为n的有序序列为止,这种排序方法称为2路归并排序。 时间复杂度为
O(nlogn),空间复杂度为O(nlogn),如果非递归实现归并,则避免了递归时深度为logn的栈空间 空间复杂度为O(n)
六、堆排序
堆是具有下列性质的完全二叉树:每个节点的值都大于或等于其左右孩子节点的值,称为大顶堆或者每个节点的值都小于或等于其左
右孩子节点的值,称为小顶堆。 堆排序就是利用堆进行排序的方法.基本思想是:将待排序的序列构造成一个大顶堆.此时,整个序列的最大值就是堆顶 的根结点.将它移
走(其实就是将其与堆数组的末尾元素交换, 此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元
素的次大值.如此反复执行,便能得到一个有序序列了。 时间复杂度为 O(nlogn),好于冒泡,简单选择,直接插入的O(n^2)
七、快速排序
通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。时间复杂度为O(nlogn)
下文没有给出快速排序的实现参考以前的文章。
#includeiostream using namespace std;
void swap1(int *left, int *right) { int temp *left; *left *right; *right temp; }
void swap2(int left, int right) { int temp left; left right; right left; }
void swap3(int left, int right) { if (left ! right) { left ^ right; right ^ left; left ^ right; } }
/*****************************************************************/ /* 冒泡排序时间复杂度最好的情况为O(n),最坏的情况是O(n^2) * 基本思想是:两两比较相邻记录的关键字,如果反序则交换 */
void BubbleSort1(int arr[], int num) { int i, j; for (i 0; i num; i) { for (j 1; j num - i; j) { if (arr[j - 1] arr[j]) swap1(arr[j - 1], arr[j]); } } }
// 改进思路设置标志位明显如果有一趟没有发生交换flag flase)说明排序已经完成. void BubbleSort2(int arr[], int num) { int k num; int j; bool flag true; while (flag) { flag false; for (j 1; j k; j) { if (arr[j - 1] arr[j]) { swap1(arr[j - 1], arr[j]); flag true; } } k--; } } //改进思路记录一轮下来标记的最后位置下次从头部遍历到这个位置就Ok void BubbleSort3(int arr[], int num) { int k, j; int flag num; while (flag 0) { k flag; flag 0; for (j 1; j k; j) { if (arr[j - 1] arr[j]) { swap1(arr[j - 1], arr[j]); flag j; } } } } /*************************************************************************/
/**************************************************************************/ /*插入排序: 将一个记录插入到已经排好序的有序表中, 从而得到一个新的,记录数增1的有序表 * 时间复杂度也为O(n^2), 比冒泡法和选择排序的性能要更好一些 */
void InsertionSort(int arr[], int num) { int temp; int i, j; for (i 1; i num; i) { temp arr[i]; for (j i; j 0 arr[j - 1] temp; j--) arr[j] arr[j - 1]; arr[j] temp; } }
/****************************************************************************/
/*希尔排序:先将整个待排元素序列分割成若干子序列由相隔某个“增量”的元素组成的分别进行 直接插入排序然后依次缩减增量再进行排序待整个序列中的元素基本有序增量足够小时 再对全体元素进行一次直接插入排序增量为1。其时间复杂度为O(n^3/2),要好于直接插入排序的O(n^2) */ void ShellSort(int *arr, int N) { int i, j, increment; int tmp; for (increment N / 2; increment 0; increment / 2) { for (i increment; i N; i) { tmp arr[i]; for (j i; j increment; j - increment) { if (arr[j - increment] tmp) arr[j] arr[j - increment]; else break; } arr[j] tmp; } } }
/**************************************************************************/
/* 简单选择排序(simple selection sort) 就是通过n-i次关键字之间的比较,从n-i1 * 个记录中选择关键字最小的记录,并和第i(1in)个记录交换之 * 尽管与冒泡排序同为O(n^2),但简单选择排序的性能要略优于冒泡排序 */
void SelectSort(int arr[], int num) { int i, j, Mindex; for (i 0; i num; i) { Mindex i; for (j i 1; j num; j) { if (arr[j] arr[Mindex]) Mindex j; } swap1(arr[i], arr[Mindex]); } }
/********************************************************************************/ /*假设初始序列含有n个记录,则可以看成n个有序的子序列,每个子序列的长度为1,然后 * 两两归并,得到(不小于n/2的最小整数)个长度为2或1的有序子序列,再两两归并,... * 如此重复,直至得到一个长度为n的有序序列为止,这种排序方法称为2路归并排序 * 时间复杂度为O(nlogn),空间复杂度为O(nlogn),如果非递归实现归并,则避免了递归时深度为logn的栈空间 * 空间复杂度为O(n) */ /*lpos is the start of left half, rpos is the start of right half*/ void merge(int a[], int tmp_array[], int lpos, int rpos, int rightn) { int i, leftn, num_elements, tmpos; leftn rpos - 1; tmpos lpos; num_elements rightn - lpos 1; /*main loop*/ while (lpos leftn rpos rightn) if (a[lpos] a[rpos]) tmp_array[tmpos] a[lpos]; else tmp_array[tmpos] a[rpos]; while (lpos leftn) /*copy rest of the first part*/ tmp_array[tmpos] a[lpos]; while (rpos rightn) /*copy rest of the second part*/ tmp_array[tmpos] a[rpos]; /*copy array back*/ for (i 0; i num_elements; i, rightn--) a[rightn] tmp_array[rightn]; } void msort(int a[], int tmp_array[], int left, int right) { int center; if (left right) { center (right left) / 2; msort(a, tmp_array, left, center); msort(a, tmp_array, center 1, right); merge(a, tmp_array, left, center 1, right); } }
void merge_sort(int a[], int n) { int *tmp_array; tmp_array (int *)malloc(n * sizeof(int)); if (tmp_array ! NULL) { msort(a, tmp_array, 0, n - 1); free(tmp_array); } else printf(No space for tmp array!\n); }
/************************************************************************************/ /* 堆是具有下列性质的完全二叉树:每个节点的值都大于或等于其左右孩子节点的值,称为大顶堆 * 或者每个节点的值都小于或等于其左右孩子节点的值,称为小顶堆*/
/*堆排序就是利用堆进行排序的方法.基本思想是:将待排序的序列构造成一个大顶堆.此时,整个序列的最大值就是堆顶 * 的根结点.将它移走(其实就是将其与堆数组的末尾元素交换, 此时末尾元素就是最大值),然后将剩余的n-1个序列重新 * 构造成一个堆,这样就会得到n个元素的次大值.如此反复执行,便能得到一个有序序列了 */ /* 时间复杂度为 O(nlogn),好于冒泡,简单选择,直接插入的O(n^2) */
// 构造大顶堆 #define leftChild(i) (2*(i) 1)
void percDown(int *arr, int i, int N) { int tmp, child; for (tmp arr[i]; leftChild(i) N; i child) { child leftChild(i); if (child ! N - 1 arr[child 1] arr[child]) child; if (arr[child] tmp) arr[i] arr[child]; else break; } arr[i] tmp; }
void HeapSort(int *arr, int N) { int i; for (i N / 2; i 0; i--) percDown(arr, i, N); for (i N - 1; i 0; i--) { swap1(arr[0], arr[i]); percDown(arr, 0, i); } } int main(void) { int arr[] { 9, 2, 5, 8, 3, 4, 7, 1, 6, 10}; HeapSort(arr, 10); for (int i 0; i 10; i) cout arr[i] ; cout endl; return 0; }
注上述7种都是比较排序下面3种都是非比较排序理论上可以达到O(n)比比较排序要快但是这3种都是有其应用背景才能发挥作用的否则适得其反。
八计数排序
计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。 算法的步骤如下
找出待排序的数组中最大和最小的元素 统计数组中每个值为i的元素出现的次数存入数组C的第i项 对所有的计数累加从C中的位置为1的元素开始每一项和前一项相加 反向填充目标数组将每个元素i放在新数组的第C(i)项每放一个元素就将C(i)减去1 由于用来计数的数组C的长度取决于待排序数组中数据的范围等于待排序数组的最大值与最小值的差加上1这使得计数排序对于数据范围很大的数组需要大量时间和内存。 九桶排序
桶排序 (Bucket sort)或所谓的箱排序是一个排序算法工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序
桶排序以下列程序进行
设置一个定量的数组当作空桶子。 寻访串行并且把项目一个一个放到对应的桶子去。hash 对每个不是空的桶子进行排序。 从不是空的桶子里把项目再放回原来的串行中。
十基数排序 基数排序英语Radix sort是一种非比较型整数排序算法其原理是将整数按位数切割成不同的数字然后按每个位数分别比较。由于整数也可以表达字符串比如名字或日期和特定格式的浮点数所以基数排序也不是只能使用于整数。
它是这样实现的将所有待比较数值正整数统一为同样的数位长度数位较短的数前面补零。然后从最低位开始依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的方式可以采用LSDLeast significant digital或MSDMost significant digitalLSD的排序方式由键值的最右边开始而MSD则相反由键值的最左边开始。 C Code #includestdio.h #includestring.h #includealgorithm
using namespace std;
/*****************计数排序*******************************/ void CountSort(int *arr, int num) { int mindata arr[0]; int maxdata arr[0]; for (int i 1; i num; i) { if (arr[i] maxdata) maxdata arr[i]; if (arr[i] mindata) mindata arr[i]; } int size maxdata - mindata 1; //申请空间并初始化为0 int *pCount (int *)malloc(sizeof(int) * size); memset(pCount, 0, sizeof(int)*size); //记录排序计数每出现一次在对应位置加1 for (int i 0; i num; i) pCount[arr[i]-mindata]; //确定不比该位置大的数据个数 for (int i 1; i size; i) pCount[i] pCount[i - 1]; //加上前一个的计数 int *pSort (int *)malloc(sizeof(int) * num); memset((char*)pSort, 0, sizeof(int) * num); //从末尾开始拷贝是为了重复数据首先出现的排在前面即稳定排序 for (int i num - 1; i 0; i--) { //包含自己需要减1重复数据循环回来也需要减1 --pCount[arr[i]-mindata]; pSort[pCount[arr[i]-mindata]] arr[i]; } //拷贝到原数组 for (int i 0; i num; i) arr[i] pSort[i]; free(pCount); free(pSort);
}
/*****************桶排序*****************************/ struct Node { int key_; struct Node *next_; Node(int key) { key_ key; next_ NULL; } };
#define bucket_size 10 //与数组元素个数相等
void buck_sort(int arr[], int num) { Node *bucket_table[bucket_size]; memset(bucket_table, 0, sizeof(bucket_table)); //建立每一个头节点,头节点的key保存当前桶的数据量 for (int i 0; i bucket_size; i) bucket_table[i] new Node(0); int maxValue arr[0]; for (int i 1; i num; i) { if (arr[i] maxValue) maxValue arr[i]; } for (int j 0; j num; j) { Node *ptr new Node(arr[j]);//其余节点的key保存数据 //映射函数计算桶号 // index (value * number_of_elements) / (maxvalue 1) int index (arr[j] * bucket_size) / (maxValue 1); Node *head bucket_table[index]; //该桶还没有数据 if (head-key_ 0) { bucket_table[index]-next_ ptr; (bucket_table[index]-key_); } else { //找到合适的位置插入 while (head-next_ ! NULL head-next_-key_ ptr-key_) head head-next_; ptr-next_ head-next_; head-next_ ptr; (bucket_table[index]-key_); } } //将桶中的数据拷贝回原数组 int m, n; for (m 0, n 0; n num m bucket_size; m, n) { Node *ptr bucket_table[m]-next_; while (ptr ! NULL) { arr[n] ptr-key_; ptr ptr-next_; n; } n--; } //释放分配的动态空间 for (m 0; m bucket_size; m) { Node *ptr bucket_table[m]; Node *tmp NULL; while (ptr ! NULL) { tmp ptr-next_; delete ptr; ptr tmp; } }
} /****************************************************/
/******************** 基数排序LSD*********************/
void base_sort_ISD(int *arr, int num) { Node *buck[10]; // 创建一个链表数组 Node *tail[10]; //保存每条链表尾节点指针集合 //这样插入buck数组时就不用每次遍历到末尾 int i, MaxValue, kth, high, low; Node *ptr; for(MaxValue arr[0], i 1; i num; i) MaxValue max(MaxValue, arr[i]); memset(buck, 0, sizeof(buck)); memset(tail, 0, sizeof(buck)); for(low 1; high low * 10, low MaxValue; low * 10) { //只要没排好序就一直排序 for(i 0; i num; i) { //往桶里放 kth (arr[i] % high) / low;//取出数据的某一位作为桶的索引 ptr new Node(arr[i]); //创建新节点 //接到末尾 if (buck[kth] ! NULL) { tail[kth]-next_ ptr; tail[kth] ptr; } else { buck[kth] ptr; tail[kth] ptr; } } //把桶中的数据放回数组中同条链表是从头到尾 for (kth 0, i 0; kth num; i) { while (buck[i] ! NULL) { arr[kth] buck[i]-key_; ptr buck[i]; buck[i] buck[i]-next_; delete ptr; } } memset(tail, 0, sizeof(buck)); }
} /**************************************************************/
int main(void) { int arr1[] {10, 15, 11, 20, 15, 18, 19, 12, 14, 17}; int size1 sizeof(arr1) / sizeof(arr1[0]); CountSort(arr1, size1); for (int i 0; i size1; i) printf(%d , arr1[i]); printf(\n); int arr2[] {54, 8, 216, 512, 27, 729, 0, 1, 343, 125}; int size2 sizeof(arr2) / sizeof(arr2[0]); base_sort_ISD(arr2, size2); for (int i 0; i size2; i) printf(%d , arr2[i]); printf(\n); int arr3[] {49, 38, 65, 97, 76, 13, 27, 49, 132, 134}; int size3 sizeof(arr3) / sizeof(arr3[0]); buck_sort(arr3, size3); for (int i 0; i size3; i) printf(%d , arr3[i]); printf(\n); return 0; }
输出为
