1.直接插入排序
摸牌后给手头上的排整理顺序的一个过程,其实就是一种简单的直接插入排序
直接插入排序的基本思想就是:把第一个元素看成有序,然后将待排序的数组元素一个一个插入到有序序列中,直到所有元素都插完为止,从而形成新的有序序列.
举个例子:12,4,46,23,541,32
第一趟:4,12 46,23,541,32
第二趟:4,12,46 23,541,32
第三趟4,12,23,46 541,32
第四趟:4,12,23,46,541 32
第五趟:4,12,23,32,46,541
插入总趟数:5趟(第一个12不用插入)直接就是有序的,end从下标0开始
void InsertSort(int* a, int n) { //n个数据,第一个默认有序,因此只需进行n-1趟插入排序 for (int i = 0; i < n - 1; i++) { //定义end为已有序序列的数元素的下标的最大值为i int end = i; //定义待排序的元素的下标中的最小值对应的元素为temp int temp = a[i + 1]; //每一趟进行插入排序 while (end >= 0) { //如果已有序序列的元素a[end]比待排序的元素temp大,则将a[end]后移一位 if (a[end] > temp) { a[end + 1] = a[end]; end--; } else//否则就退出循环 { break; } } //跳出while循环有两种情况: //1.end<0,也就是说已有序序列的所有元素都比完了,也就是待排序的那个元素比已有序序列的所有元素都小 //2.待排序的元素temp比已有序序列的某元素a[end]大,提前跳出循环 //将temp放在下标为end+1的位置 a[end + 1] = temp; } }
加上数据测试:
//直接插入排序,假设排升序 void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { int end = i; int temp = a[i + 1]; while (end >= 0) { if (a[end] > temp) { a[end + 1] = a[end]; end--; } else { break; } } a[end + 1] = temp; } } void PrintArr(int* a, int sz) { for (int i = 0; i < sz; i++) { printf("%d\t", a[i]); } } int main() { int a[] = { 12,4,46,23,541,32 }; int sz = sizeof(a) / sizeof(a[0]); InsertSort(a, sz); PrintArr(a, sz); return 0; }
时间复杂度:O(n^2)
最坏的情况:当我们要排升序(降序),但是原数组是降序(升序) ,O(n^2)
最好的情况:当我们要排升序(降序),且是原数组是接近升序(降序) ,while处变成只比较了一次,O(n)
2.希尔排序
希尔排序的步骤:
- 预排序--->使得原数组先接近排序(先大幅度调整)
- 直接插入排序(后小幅度调整)
2-1.预排序
整体思路:先将间隔为gap分为一组,对每一组进行插入排序
假设gap=3;
关于gap的设置:
首先gap设置成一个常数肯定不行,因为这个gap得要和数组元素个数n得大小适应, n大gap大,n小gap小.所以gap初始化为n.第一次进for循环得gap是gap/3
当gap迭代得时候入如果给gap=gap/3得话,假如数组元素个数为n,gap进for得时候就是0,等于没排序了,所以加一个gap=gap/3+1,这个3是可以变化得,这个1保证最少要直接插入排序,以防万一.(如果不加1,当n=6时,就会进入2的死循环,所以要加上1<但是也可以改成gap/=2,那么除出来的结果就是1和0了,但是这样的话就不太好,因为间隔太小)
void ShellSort(int* a, int n) { int gap = n; while (gap > 1 ) { gap = gap / 3 + 1; for (int i = 0; i < n - gap; i++) { int end = i; int temp = a[end + gap]; while (end >= 0) { if (a[end] > temp) { a[end + gap] = a[end]; end = end - gap; } else { break; } } a[end + gap] = temp; } printf("gap==%d:", gap); PrintArr(a, n); } } int main() { int a[] = {9,1,2,5,7,4,8,6,3,5 }; int sz = sizeof(a) / sizeof(a[0]); ShellSort(a, sz); return 0; }
希尔排序的时间复杂度很难算:根据前人算的结果大概时n的1.3此方,当数据量很大的时候,时间复杂度略逊与nlogn
3.性能测试代码
这个性能测试代码是通过计算排序算法消耗的时间，从而测试排序算法的效率
担心栈溢出，所以选择在堆上开辟一块大空间
通过记录排序前后clock()时钟打点记录的时间（毫秒），end-bigin即是排序消耗的时间
//C 语言中的clock()函数的头文件是time.h int main() { srand((unsigned int)0); int N = 100000; int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; i++) { a1[i] = rand(); a2[i] = a1[i]; } int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); printf("InsertSort：%d\n", end1-begin1); int begin2 = clock(); InsertSort(a2, N); int end2 = clock(); printf("ShellSort：%d\n", end2-begin2); free(a1); free(a2); a1 = a2 = NULL; return 0; }
4.链表直接插入排序OJ
由上面我们知道，如果和数组排序从后往前比较的话，由于链表只能顺序遍历的特点，这是不可取的，所以我们只能从前往后比进行插入，加之链表插入元素时不用大量移动元素，真是完美！
第一步：建立新链表，从原链表中取出结点，记为cur
第二步：从前往后遍历新链表，比较newcur->val和cur->val的大小，选择合适的位置插入
以下是带头结点的链表排序，如果不带头结点，要注意头插的newprev为空的特殊情况！！
struct ListNode* insertionSortList(struct ListNode* head){ //第一步:建立新链表，从原链表中取出结点，记为cur struct ListNode* Guard=(struct ListNode*)malloc(sizeof(struct ListNode)); Guard->next=head; struct ListNode* cur=head->next; head->next=NULL; //第二步:从前往后遍历新链表，比较newcur->val和cur->val的大小，选择合适的位置插入 while(cur) { struct ListNode* next=cur->next; struct ListNode* newprev=Guard; struct ListNode* newcur=Guard->next; while(newcur) { if(cur->val>newcur->val) { newprev=newcur; newcur=prev->next; } else { break; } } prev->next=cur; cur->next=newcur; cur=next; } struct ListNode* newhead=Guard->next; free(Guard); Guard=NULL; return newhead; }
