二分查找
循环二分查找
int BinaryFindValue(const int* ar, int n, int val)//循环的二分查询 { assert(ar != NULL); // NULL nullptr; int pos = -1; int left = 0, right = n - 1; while (left <= right) // left < right { //int mid = (right + left) / 2;//可能左右相加超出整形数组的范围， int mid = (right - left) / 2 + left;// if (val < ar[mid]) { right = mid - 1; } else if (val > ar[mid]) { left = mid + 1; } else { while (mid > left && ar[mid - 1] == val) { mid = mid - 1; } pos = mid; break; } } return pos; } int main() { int ar[] = { 12,23,34,45,56,67,78,89,90,100 }; int n = sizeof(ar) / sizeof(ar[0]); int val; cin >> val; int pos = BinaryFindValue(ar, n, val);//二分查询 cout << pos << endl; return 0; }
递归二分查找
int FindValue(const int* ar, int left, int right, int val) { int pos = -1; if (left <= right) { int mid = (right - left) / 2 + left; if (val < ar[mid]) { pos = FindValue(ar, left, mid - 1, val); } else if (val > ar[mid]) { pos = FindValue(ar, mid + 1, right, val); } else { pos = mid; } } return pos; } //递归的二分查询 int BinFindValue(const int* ar, int n, int val) { assert(ar != nullptr); return FindValue(ar, 0, n - 1, val); } int main() { int ar[] = { 12,23,34,45,56,67,78,89,90,100 }; int n = sizeof(ar) / sizeof(ar[0]); int val; cin >> val; pos = BinFindValue(ar, n, val);//递归的二分查询 cout << pos << endl; return 0; }
快速排序法
递归
void Print_Ar(int* ar, int n) { for (int i = 0; i < n; ++i) { printf("%4d ", ar[i]); } printf("\n"); } int Parition(int* ar, int left, int right) { int tmp = ar[left]; while (left < right) { while (left < right && tmp < ar[right]) --right; if (left < right) ar[left] = ar[right]; while (left < right && ar[left] <= tmp) ++left; if (left < right) ar[right] = ar[left]; } ar[left] = tmp; return left; } void QuickPass(int* ar, int left, int right)//快速排序 { if (left < right) { int pos = OneParition(ar, left, right); QuickPass(ar, left, pos - 1); QuickPass(ar, pos + 1, right); } } void QuickSort(int* ar, int n)//快排 { assert(ar != NULL); QuickPass(ar, 0, n - 1); } int main() { int ar[] = { 56,23,34,89,90,12,78,45,56,100,67 }; int n = sizeof(ar) / sizeof(ar[0]); Print_Ar(ar, n); QuickSort(ar, n); Print_Ar(ar, n); return 0; }
栈、
void NiceQuickSort(int* ar, int n) { assert(ar != nullptr); stack<int> ist; ist.push(0); ist.push(n - 1); while (!ist.empty()) { int right = ist.top(); ist.pop(); int left = ist.top(); ist.pop(); int pos = Parition(ar, left, right); if (left < pos - 1) { ist.push(left); ist.push(pos - 1); } if (pos + 1 < right) { ist.push(pos + 1); ist.push(right); } } }
队列
void NiceQuickSort(int* ar, int n) { assert(ar != nullptr); queue<int> ist; ist.push(0); ist.push(n - 1); while (!ist.empty()) { int left = ist.front(); ist.pop(); int right = ist.front(); ist.pop(); int pos = Parition(ar, left, right); if (left < pos - 1) { ist.push(left); ist.push(pos - 1); } if (pos + 1 < right) { ist.push(pos + 1); ist.push(right); } } }
队的另一种方法：
void NiceQuickSort(int* ar, int n) { assert(ar != nullptr); queue<std::pair<int, int> > ist;//pair 一对 有first,second std::pair<int, int> LR(0, n - 1); ist.push(LR); while (!ist.empty()) { std::pair<int, int> LR = ist.front(); ist.pop(); int pos = RandParition(ar, LR.first, LR.second); if (LR.first < pos - 1) { ist.push(pair<int, int>(LR.first, pos - 1)); } if (pos + 1 < LR.second) { ist.push(pair<int, int>(pos + 1, LR.second)); } } }
若数据本来有序，（若从第一个开始划分，变成冒泡排序）
使用随机法
int Parition(int* ar, int left, int right) { int tmp = ar[left]; while (left < right) { while (left < right && tmp < ar[right]) --right; if (left < right) ar[left] = ar[right]; while (left < right && ar[left] <= tmp) ++left; if (left < right) ar[right] = ar[left]; } ar[left] = tmp; return left; } int RandParition(int* ar, int left, int right) { assert(ar != nullptr); int index = rand() % (right - left + 1) + left; //模值加left,模值得到的是第几位，而不是物理下标，加left得到那一位的物理下标 std::swap(ar[index], ar[left]); return Parition(ar, left, right); }
适合单链表的：冒泡，选择
从一头进行逼近
int OneParition(int* ar, int left, int right) { int i = left, j = left - 1; int tmp = ar[i]; while (i <= right) { if (ar[i] <= tmp) { j = j + 1; std::swap(ar[i], ar[j]); } ++i; } std::swap(ar[left], ar[j]); return j; }
单链表的快排
含头结点的快排：
typedef int ElemType; typedef struct ListNode { ElemType data; struct ListNode* next; }ListNode, * LinkList; struct ListNode* Buynode() { struct ListNode* s = (struct ListNode*)malloc(sizeof(struct ListNode)); if (NULL == s) exit(1); memset(s, 0, sizeof(struct ListNode)); return s; } struct ListNode* InitList() { struct ListNode* s = Buynode(); return s; } void Push_Front(LinkList phead, ElemType val) { ListNode* s = Buynode(); s->data = val; s->next = phead->next; phead->next = s; } void PrintList(LinkList phead) { ListNode* p = phead; while (p != nullptr) { printf("%d ", p->data); p = p->next; } printf("\n"); } ListNode* Parition(ListNode* first, ListNode* end) { ListNode* jp = first; ListNode* ip = first->next;//ip指向第一个数据的结点 int tmp = ip->data; while (ip != end) { if (ip->data <= tmp) { jp = jp->next; std::swap(jp->data, ip->data);//交换函数 } ip = ip->next; } std::swap(first->data, jp->data);//退出后第一个与jp指向的交换 return jp; } void QuickPass(ListNode* first, ListNode* end) { if (first != end)//first指第一个结点，end指向的是空 { ListNode* pos = Parition(first, end); QuickPass(first, pos); QuickPass(pos, end); } } void QuickSort(ListNode* phead) { assert(phead != nullptr); QuickPass(phead, NULL); } int main() { int ar[] = { 56,23,34,89,90,12,78,45,100,67 }; int n = sizeof(ar) / sizeof(ar[0]); LinkList head = InitList(); for (int i = n - 1; i >= 0; --i) { Push_Front(head, ar[i]); } PrintList(head); QuickSort(head); PrintList(head); return 0; }
不含头结点的快排：
typedef int ElemType; typedef struct ListNode { ElemType data; struct ListNode* next; }ListNode, * LinkList; struct ListNode* Buynode() { struct ListNode* s = (struct ListNode*)malloc(sizeof(struct ListNode)); if (NULL == s) exit(1); memset(s, 0, sizeof(struct ListNode)); return s; } struct ListNode* InitList() { struct ListNode* s = Buynode(); return s; } ListNode* Push_Front(LinkList phead, ElemType val) { if (phead == nullptr) { ListNode* s = Buynode(); s->data = val; s->next = nullptr; return s; } ListNode* s = Buynode(); s->data = val; s->next = phead; phead = s; return phead; } void PrintList(LinkList phead) { ListNode* p = phead; while (p != nullptr) { printf("%d ", p->data); p = p->next; } printf("\n"); } ListNode* Parition(ListNode* first, ListNode* end) { ListNode* jp = first; ListNode* ip = first->next;//ip指向第一个数据的结点 int tmp = jp->data; while (ip != end) { if (ip->data <= tmp) { jp = jp->next; std::swap(jp->data, ip->data);//交换函数 } ip = ip->next; } std::swap(first->data, jp->data);//退出后第一个与jp指向的交换 return jp; } void QuickPass(ListNode* first, ListNode* end) { if (first != end)//first指第一个结点，end指向的是空 { ListNode* pos = Parition(first, end); QuickPass(first, pos); QuickPass(pos->next, end); } } void QuickSort(ListNode* phead) { assert(phead != nullptr); QuickPass(phead, NULL); } int main() { int ar[] = { 56,23,34,89,90,12,78,45,100,67 }; int n = sizeof(ar) / sizeof(ar[0]); LinkList head = nullptr; for (int i = n - 1; i >= 0; --i) { head = Push_Front(head, ar[i]); } PrintList(head); QuickSort(head); PrintList(head); return 0; }
寻找第k小的值：
int Parition(int* ar, int left, int right) { int tmp = ar[left]; while (left < right) { while (left < right && tmp < ar[right]) --right; if (left < right) ar[left] = ar[right]; while (left < right && ar[left] <= tmp) ++left; if (left < right) ar[right] = ar[left]; } ar[left] = tmp; return left; } int SelectK(int* ar, int left, int right, int k) { if (left == right && k == 1) return ar[left];//此时下标只有一个值 int pos = Parition(ar, left, right); int j = pos - left + 1; if (k <= j) return SelectK(ar, left, pos, k); else return SelectK(ar, pos + 1, right, k - j); } int Select_K_Min(int* ar, int n, int k)//找第k小 { assert(ar != NULL && k >= 1 && k <= n); return SelectK(ar, 0, n - 1, k); } int main() { int ar[] = { 56,23,34,89,90,12,78,45,100,67 }; int n = sizeof(ar) / sizeof(ar[0]); for (int k = 1; k <= n; ++k) { printf("%d => %d \n", k, Select_K_Min(ar, n, k)); } return 0; }