sort algorithms

时间:2022-09-10 13:26:34

//todo

#include<iostream>

void swap(int *a, int *b){int temp = *a; *a = *b; *b = temp;}
void print_array(int *arr, int len) { for (int i = ; i < len; i++) std::cout << arr[i] << " , "; } // swap sort (bubble sort), bubble the largest item to top of list, impractical
void bubble_sort(int arr[], int len)
{
bool need_sort = true;
while (need_sort)
{
need_sort = false;
for (int i = ; i < len - ; i++)
{
if (arr[i] < arr[i + i]){swap(arr+i, arr+i + );need_sort = true;}
}
}
} // selection sort, select the largest one, and put it in the top, just need O(n) insert operation!!!
void select_sort(int arr[], int len)
{
for (int i = ; i < len - ; i++)
{
int index = i;
for (int j = i + ; j < len; j++)
{
if (arr[j] > arr[index]) index = j;
}
swap(arr+i, arr+index);
}
} // the only advantage of both bubble sort and selection sort is easy to implement, should not use it // insert sort, choose item in list one and insert into another in right order
// efficient for small lists and mostly-sorted list
void insert_sort(int arr[], int len)
{
for (int i = ; i < len-; i++)
{
int temp = arr[i + ];
int j = i;
for (; j >= && (arr[j] < temp); j--)
{
arr[j+] =arr[j];
}
if (j < i) arr[j+] = temp;
}
} // as the result list is sorted, insert one new item is same to : put the new item in the top,
// bubble (swap) it to the right position (just need one-time bubbling through the list)
void insert_sort2(int arr[], int len)
{
for (int i = ; i < len; i++)
{
for (int j = i - ; j >= && (arr[j] < arr[j + ]); j--)
{
swap(arr + j, arr + j + );
}
}
} // shell sort, combine insert sort and group (because insert sort is efficient when the list is mostly-sorted,
// one of the fastest algorithms for small number of elements( < 1000 ), and it needs little momery
// unlike efficient sorting algorithms, Shellsort does not require use of the call stack, making it useful in embedded systems where memory is at a premium
void shell_sort(int arr[], int len)
{
for (int gap = len / ; gap >; gap /= )
{
for (int i = ; i < gap; i++)
{
for (int k = i + gap; k < len; k += gap)
{
for (int j = k - gap; j >= && (arr[j] < arr[j + gap]); j -= gap) swap(arr + j, arr + j + gap);
}
}
}
} // merge sort, recursion and double memory of data
void merge_sorted_array(int a[], int lena, int b[], int lenb, int c[])
{
int i(), j(), m();
while (i < lena && j << lenb)
{
if (a[i] < b[j]) c[m++] = a[i++];
else c[m++] = b[j++];
}
while (i < lena) c[m++] = a[i++];
while (j < lenb) c[m++] = b[j++];
} void merge_array(int a[], int first,int mid, int last, int temp[])
{
int i(first), j(mid), m();
while (i < mid && j <=last)
{
if (a[i] < a[j]) temp[m++] = a[i++];
else temp[m++] = a[j++];
}
while (i < mid) temp[m++] = a[i++];
while (j <=last) temp[m++] = a[j++]; for (i = first, m = ; i <= last;) a[i++] = temp[m++];
} void merge_sort(int a[], int first_index, int last_index, int temp[])
{
if (last_index>first_index)
{
int mid = (first_index + last_index) / ;
merge_sort(a, first_index, mid, temp);
merge_sort(a, mid + , last_index, temp);
merge_array(a, first_index, mid+, last_index, temp);
}
} // quick sort, choose a pivot, put all elements smaller before it!
// Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms
// in-place, need less swap than merge-sort
void quick_sort(int a[], int first, int last)
{
if (!(first < last)) return;
int i = first, j = last, temp = a[i];
while (i < j)
{
while (i < j && temp < a[j]) j--;
if (i < j) a[i++] = a[j];
while (i < j && a[i] < temp) i++;
if (i < j) a[j--] = a[i];
}
a[i] = temp;
quick_sort(a, first, i - );
quick_sort(a, i + , last);
} int main()
{
int array01[] = { , , , , , , , , };
int temparr[] = { };
quick_sort(array01, ,);
print_array(array01, );
}

sort algorithms的更多相关文章

  1. Basic Sort Algorithms

    1. Bubble Sort public void bubbleSort(int[] arr) { boolean swapped = true; int j = 0; int tmp; while ...

  2. Advanced Sort Algorithms

    1. Merge Sort public class Mergesort { private int[] numbers; private int[] helper; private int numb ...

  3. Javascript数组算法和技巧总结

    Js-arrayMethod https://github.com/HerbertKarajan/Js-arrayMethod List unique an array 数组去重 random str ...

  4. Java性能提示(全)

    http://www.onjava.com/pub/a/onjava/2001/05/30/optimization.htmlComparing the performance of LinkedLi ...

  5. Java Concurrency - invokeAny &amp&semi; invokeAll

    Running multiple tasks and processing the first result A common problem in concurrent programming is ...

  6. AOJ&sol;初等排序习题集

    ALDS1_1_D-MaximumProfit. Codes: //#define LOCAL #include <cstdio> #include <algorithm> u ...

  7. LeetCode Questions List (LeetCode 问题列表)- Java Solutions

    因为在开始写这个博客之前,已经刷了100题了,所以现在还是有很多题目没有加进来,为了方便查找哪些没加进来,先列一个表可以比较清楚的查看,也方便给大家查找.如果有哪些题目的链接有错误,请大家留言和谅解, ...

  8. BookNote&colon; Refactoring - Improving the Design of Existing Code

    BookNote: Refactoring - Improving the Design of Existing Code From "Refactoring - Improving the ...

  9. Lazarus教程 中文版后续给出

    市面上有介绍Delphi的书籍(近来Delphi的书也是越来越少了),但没有一本系统的介绍Lazarus的书,这本书是网上的仅有的一本Lazarus教程,目前全部是英文,不过我已经着手开始翻译,争取尽 ...

随机推荐

  1. MVC之前的那点事儿系列(4):Http Pipeline详细分析(上)

    文章内容 继续上一章节的内容,通过HttpApplicationFactory的GetApplicationInstance静态方法获取实例,然后执行该实例的BeginProcessRequest方法 ...

  2. WPF TreeView的使用

    WPF提供了treeView控件,利用该控件开发者可以将数据分层显示在树结构中.当然其中需要用到Binding的机制,有用的类包括:ObjectDataProvider.DataTemplate.Hi ...

  3. TIOBE 2015年5月编程语言排行榜 Visual Studio系列在上升

    TIOBE 编程语言社区排行榜是编程语言流行趋势的一个指标,每月更新,这份排行榜排名基于互联网上有经验的程序员. 课程和第三方厂商的数量.排名使用著名的搜索引擎(诸如 Google.MSN.Yahoo ...

  4. glusterfs repo

    Installing Gluster For RPM based distributions, if you will be using InfiniBand, add the glusterfs R ...

  5. SQL点滴13—收集SQLServer线程等待信息

    原文:SQL点滴13-收集SQLServer线程等待信息 要知道线程等待时间是制约SQL Server效率的重要原因,这一个随笔中将学习怎样收集SQL Server中的线程等待时间,类型等信息,这些信 ...

  6. UIBezierPath与CAShapeLayer结合画扇形

    /*让半径等于期望半径的一半 lineWidth等于期望半径 就可以画圆*/ 可以看出layer的走势是从圆边的中间一半在圆外 一半在圆内 因此让半径等于期望半径的一半 lineWidth等于期望半径 ...

  7. Android系统--输入系统(十三)Dispatcher线程情景分析&lowbar;Reader线程传递事件

    Android系统--输入系统(十三)Dispatcher线程情景分析_Reader线程传递事件 1. 输入按键 我们知道Android系统的按键分为三类:(1)Global Key;(2)Syste ...

  8. &lpar;一&rpar;V4L2学习流程

    title: V4L2学习流程 date: 2019/4/23 18:00:00 toc: true --- V4L2学习流程 参考资料 关键资料,插图让人一下子就理解了 Linux摄像头驱动1--v ...

  9. 【MOS】在不同版本和平台之间进行还原或复制 &lpar;文档 ID 1526162&period;1&rpar;--跨版本恢复

    参考链接:http://blog.itpub.net/26736162/viewspace-1549041/

  10. sqli-labs:23&sol;25-28,绕waf

    sqli23: and|or型报错 ' or extractvalue(1,concat(0x7e,database())) or '1'='1 union型嵌套select ' union sele ...