|
排序
//冒泡排序
//输入n个数字排序 (1-n)或者
(0-(n-1))
//冒泡排序一共需执行n-1趟 (若是从大到小排序)每趟排序都会把最小的放在最后所以每趟排序待排序的数会少一个
NSMutableArray * arr =@[@"1",@"6",@"2",@"4",@"5"];
for (int i =0; i<arr.count;
i++) {
for (int j =0; j<arr.count-i-1;
j++) {
if ([arr[j]doubleValue]<[arr[j+1]doubleValue])
{//如果后面的比前面的大交换
[arr exchangeObjectAtIndex:jwithObjectAtIndex:(j +
1)];//交换方法
}
}
}
// 选择排序
//选择排序的思想就是,每一趟选出一个最小或者最大的, 每次都与一个元素进行比较. 比如 第一趟是都与a[0]比较 选出一个最小的,第二趟都与a[1]比较,而 j 每次都是 i 的下一个
- (void)sort:(NSMutableArray *)arr
{
for (int i =0; i < arr.count;
i ++) {
for (int j = i +1; j < arr.count;
j ++) {
if ([arr[i]integerValue] > [arr[j]
integerValue]) {
int temp = [arr[i]integerValue];
arr[i] = arr[j];
arr[j] = [NSNumbernumberWithInt:temp];
}
}
}
NSLog(@"选择排序后：%@",arr);
}
//快速排序
//思想:先在待排序的序列中选择一个基数,一般都选左边第一个,然后要把这个序列中所有比这基数大的数放在右边,所有比基数小的数放在左边(由小到大排序)
//eg: 6 1 2 7 9 3 4 5 10 8 [ 6 为基数]
//定义:i为序列最左边 j为序列最右边
// j-- i ++
//如果j遇到比基数 6 小的数 就停下 然后i 动 直到i遇到比6大的数 即 j运动到5 i 运动到7 这时 7 和5 做交换
//然后j -- i ++ 继续移动 当j 运动到4 而 i运动到9 交换
//然后在3时 j和i相遇 3比6小 然后交换3和6
//这时 序列就分成了两部分 ,一部分比6小,一部分比6大 然后在利用上面的方法就排好啦
- (void)quickSort:(NSMutableArray *)arr leftIndex:(int)left rightIndex:(int)right
{
if (left < right) {
int temp = [selfgetMiddleIndex:arr
leftIndex:left rightIndex:right];
[selfquickSort:arr
leftIndex:leftrightIndex:temp -
1]; //这里调用自身函数,这种方法叫递归 一直运行到不符合条件为止.
[selfquickSort:arr
leftIndex:temp +1
rightIndex:right];
}
}
- (int)getMiddleIndex:(NSMutableArray *)arr leftIndex:(int)left rightIndex:(int)right
{
int tempValue = [arr[left]integerValue];
while (left < right) {
while (left < right && tempValue <= [arr[right]integerValue]) {
right --;
}
if (left < right) {
arr[left] = arr[right];
}
while (left < right && [arr[left]integerValue] <= tempValue) {
left ++;
}
if (left < right) {
arr[right] = arr[left];
}
}
arr[left] = [NSNumbernumberWithInt:tempValue];
return left;
}
冒泡排序和选择排序的时间复杂度都很高O(N的平方)
快速排序的最差时间复杂度和冒泡排序一样 但是它的平均时间复杂度是O(NlogN)快速排序是跳跃式排序(冒泡排序是只能和身边的比较排序),利用了二分的思想.
队列
队列只允许在队列的首部进行删除操作,即出队.而在队列的尾部进行插入操作,称为入队. 先进先出原则.
栈
后进先出原则,只能在一端进行插入和删除操作.
链表
就是通过指针指向，把两个结构体连接起来。比如定义下面这个结构体
//这个结构体是单向链表,即后继指针指向后面的节点.
struct node
{
int data; //数据空间
struct node *next; //指针空间(也称为后继指针)
}
可以看到结构体里面定义了一个自身类型的指针，通过让指针指向另外一个结构体，我们就能通过结构体里面的next变量访问下个结构体里面的内容，而通过下一个结构体，同样可以通过下一个结构体的next指向，找到下一个这种类型的结构体，这样就形成了所谓的链表。
链表的优点是：采用动态存储分配，不会造成内存浪费和溢出；另外，链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素。
单链表的逆序
思路:每次把第二个元素提到最前面来。如链表的四个元素是 头结点->a1->a2->a3->a4,第一次交换，我们先让头结点的next域指向结点a2，再让结点a1的next域指向结点a3，最后将结点a2的next域指向结点a1，就完成了第一次交换。
之后,把握住a1即可,重复上面的方法,第二次 是 头结点->a2->a1->a3->a4,这时让头结点的next域指向a3,然后a3指向a2,a1指向a4即可,直到a1的next指向空为止.
| 
转播
